LL(1)分析法实验个人感悟
时间: 2023-12-09 21:04:46 浏览: 29
在进行LL(1)分析法实验的过程中,我深刻体会到了文法的重要性。一个好的文法可以让LL(1)分析法更加高效和准确地分析句子,而一个糟糕的文法则可能会导致分析出错或者需要更多的步骤来分析句子。因此,在设计文法时需要考虑到文法的简洁性、一致性、易读性以及适应性等因素。
另外,LL(1)分析法是一种自顶向下的语法分析方法,它可以通过预测下一个输入符号来进行推导。因此,在实验中我也体会到了这种自顶向下的分析方法的优点和缺点。优点是可以方便地进行语法错误的检查和纠正,缺点是可能会出现左递归、回溯等问题,需要通过改造文法或者使用其他的分析方法来解决。
总之,通过这次实验,我对LL(1)分析法有了更深刻的理解和认识,也更加意识到了文法在语法分析中的重要性。
相关问题
ll(1)分析法c++实现
LL(1)分析法是一种自顶向下的语法分析方法,它使用一个分析表来帮助确定应该使用哪个产生式来扩展当前的非终结符。下面是一个简单的LL(1)分析法的C++实现:
```cpp
#include <iostream>
#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;
// 定义文法符号类型
enum SymbolType {
TERMINAL,
NONTERMINAL
};
// 定义文法符号类
class Symbol {
public:
SymbolType type;
string name;
Symbol(SymbolType t, const string& n) : type(t), name(n) {}
};
// 定义产生式类
class Production {
public:
Symbol nonterminal; // 非终结符
vector<Symbol> rhs; // 产生式右部
Production(const Symbol& n, const vector<Symbol>& r) : nonterminal(n), rhs(r) {}
};
// 定义LL(1)分析表类
class LL1Table {
public:
unordered_map<string, unordered_map<string, Production>> table;
// 添加一条表项
void addEntry(const string& nonterminal, const string& terminal, const Production& p) {
table[nonterminal][terminal] = p;
}
// 获取一条表项
Production getEntry(const string& nonterminal, const string& terminal) const {
auto it1 = table.find(nonterminal);
if (it1 == table.end()) {
throw "Invalid nonterminal symbol.";
}
auto it2 = it1->second.find(terminal);
if (it2 == it1->second.end()) {
throw "Invalid terminal symbol.";
}
return it2->second;
}
};
// 定义LL(1)分析器类
class LL1Parser {
public:
vector<Symbol> input; // 输入串
stack<Symbol> stack; // 符号栈
LL1Table table; // LL(1)分析表
LL1Parser(const vector<Symbol>& i, const LL1Table& t) : input(i), table(t) {
stack.push(Symbol(TERMINAL, "$")); // 栈底
stack.push(Symbol(NONTERMINAL, "S")); // 初始状态
}
// LL(1)分析
void parse() {
int ip = 0;
while (!stack.empty()) {
Symbol s = stack.top();
if (s.type == TERMINAL) { // 终结符
if (s.name == input[ip].name) {
stack.pop();
ip++;
} else {
throw "Syntax error.";
}
} else { // 非终结符
Production p = table.getEntry(s.name, input[ip].name);
stack.pop();
for (auto it = p.rhs.rbegin(); it != p.rhs.rend(); ++it) {
stack.push(*it);
}
}
}
cout << "Syntax is correct." << endl;
}
};
int main() {
// 构造LL(1)分析表
LL1Table table;
table.addEntry("S", "a", Production(Symbol(NONTERMINAL, "A"), {Symbol(TERMINAL, "a")}));
table.addEntry("S", "b", Production(Symbol(NONTERMINAL, "B"), {Symbol(TERMINAL, "b")}));
table.addEntry("A", "b", Production(Symbol(NONTERMINAL, "S"), {Symbol(TERMINAL, "b")}));
table.addEntry("B", "a", Production(Symbol(NONTERMINAL, "S"), {Symbol(TERMINAL, "a")}));
// 构造输入串
vector<Symbol> input = {Symbol(TERMINAL, "a"), Symbol(TERMINAL, "b"), Symbol(TERMINAL, "$")};
// 构造LL(1)分析器
LL1Parser parser(input, table);
// 进行LL(1)分析
parser.parse();
return 0;
}
```
这个例子是对文法S->aA | bB, A->bS, B->aS的LL(1)分析,在代码中构造了LL(1)分析表,并使用输入串进行了分析。在实际应用中,需要根据具体的文法和输入串,构造相应的LL(1)分析表。
LL(1)分析实验 c++代码
以下是一个简单的 LL(1) 分析实验的 C++ 代码示例:
```c++
#include <iostream>
#include <string>
#include <stack>
#include <unordered_map>
using namespace std;
// 定义文法符号类型
enum SymbolType {
TERMINAL, // 终结符
NONTERMINAL // 非终结符
};
// 定义产生式类型
struct Production {
string left; // 左部符号
vector<string> right; // 右部符号
};
// 定义 LL(1) 分析表类型
typedef unordered_map<string, unordered_map<string, Production>> ParsingTable;
// 获取终结符和非终结符类型
SymbolType getSymbolType(string symbol) {
if (isupper(symbol[0])) {
return NONTERMINAL;
}
return TERMINAL;
}
// 构造 LL(1) 分析表
ParsingTable buildParsingTable(vector<Production>& productions, vector<string>& terminals, vector<string>& nonterminals) {
ParsingTable table;
// 初始化分析表
for (auto nonterminal : nonterminals) {
for (auto terminal : terminals) {
table[nonterminal][terminal] = {"", {}};
}
}
// 填充分析表
for (auto production : productions) {
string left = production.left;
for (auto terminal : terminals) {
if (production.right[0] == terminal) { // 预测分析表第一项
table[left][terminal] = production;
} else if (getSymbolType(production.right[0]) == NONTERMINAL) { // 预测分析表其他项
for (auto follow : table[production.right[0]][terminal].right) {
if (follow != "#") {
table[left][follow] = production;
}
}
}
}
}
return table;
}
// LL(1) 分析器
bool parse(string input, ParsingTable& table) {
stack<string> stk;
stk.push("$"); // 结束符
stk.push(table.begin()->first); // 开始非终结符
int i = 0;
while (!stk.empty()) {
string top = stk.top();
stk.pop();
if (top == "$") { // 输入串匹配完毕
return true;
}
if (getSymbolType(top) == TERMINAL) { // 终结符
if (top == input.substr(i, 1)) {
i++;
} else {
return false;
}
} else { // 非终结符
Production production = table[top][input.substr(i, 1)];
if (production.left == "") { // 分析表中无对应产生式
return false;
} else {
for (auto it = production.right.rbegin(); it != production.right.rend(); it++) {
if (*it != "#") { // 空产生式不入栈
stk.push(*it);
}
}
}
}
}
return false;
}
int main() {
// 定义文法
vector<Production> productions = {
{"E", {"T", "E'"}},
{"E'", {"+", "T", "E'"}},
{"E'", {"#",}},
{"T", {"F", "T'"}},
{"T'", {"*", "F", "T'"}},
{"T'", {"#",}},
{"F", {"(", "E", ")"}},
{"F", {"i"}},
};
// 获取终结符和非终结符
vector<string> terminals = {"+", "*", "(", ")", "i"};
vector<string> nonterminals = {"E", "E'", "T", "T'", "F"};
// 构造 LL(1) 分析表
ParsingTable table = buildParsingTable(productions, terminals, nonterminals);
// 打印 LL(1) 分析表
for (auto nonterminal : nonterminals) {
for (auto terminal : terminals) {
Production production = table[nonterminal][terminal];
cout << nonterminal << ", " << terminal << ": ";
if (production.left == "") {
cout << "error" << endl;
} else {
cout << production.left << " -> ";
for (auto symbol : production.right) {
cout << symbol << " ";
}
cout << endl;
}
}
}
// 输入串
string input = "i+i*i$";
// LL(1) 分析
bool result = parse(input, table);
if (result) {
cout << "input " << input << " is accepted" << endl;
} else {
cout << "input " << input << " is rejected" << endl;
}
return 0;
}
```
该代码实现了一个简单的 LL(1) 分析器,包括以下功能:
- 构造文法符号类型的枚举类型 `SymbolType`。
- 定义产生式类型 `Production`,包括左部符号和右部符号序列。
- 定义 LL(1) 分析表类型 `ParsingTable`,使用 `unordered_map` 实现。
- 实现函数 `getSymbolType`,用于获取符号类型。
- 实现函数 `buildParsingTable`,用于构造 LL(1) 分析表。
- 实现函数 `parse`,用于进行 LL(1) 分析。
- 在 `main` 函数中定义文法、终结符和非终结符,构造 LL(1) 分析表,并对输入串进行 LL(1) 分析。
使用该代码,可以对输入串进行 LL(1) 分析,并输出分析结果。