-
自下而上语法分析
2020-05-06 18:43:27自上而下分析法算符优先文法构造优先关系矩阵构造优先关系分析表选择题解答题 算符优先文法 构造优先关系矩阵 构造优先关系分析表 ...在通常的语法分析中，（算符优先分析法）特别适合用于表达式的分析。 ...展开全文算符优先文法
构造优先关系矩阵
构造优先关系分析表
选择题
- 最左简单子树的末端节点构成的符号串称为句柄
- 🌟若a为终结符，则A->αaβ为 移进 项目
- 🌟LR(k)分析方法是（A）
A.从左到右分析，是否规约句柄要向后看k个输入符号的一种编译方法。 - 在通常的语法分析中，（算符优先分析法）特别适合用于表达式的分析。
- 🌟若项目集LK含有A->α. 则在状态k时，仅当面临的输入符号a属于FOLLOW(A)时，才采取“A->α”动作的一定是（SRL(1)分析法）
- 在规范规约中，任何可规约串的出现都在（栈顶）
- 自下而上语法分析的主要分析动作是（规约）
- 一个算符优先文法可能不存在算符优先函数与之对应（正确）
- LR分析法在自左至右扫描输入串时就能发现错误，但不能准确指出出错地点（正确）
解答题
1.设文法G[S]:S->(T)|a
T->T+S|S
(1) 计算FIRSTVT和LASTVT；
(2)构造优先分析表。
2.已知文法G[S]:E->E+T|T
T->T*F|F
F->(E)|I
(1)给出句型（i+i）*i+i的最左推导及画出语法树；
(2)给出句型（E+T）*i+F的短语，素短语和最左素短语；
-
编译原理实验三-自下而上语法分析及语义分析.docx.pdf
2020-07-24 17:16:15上海电力学院 编译原理 课程实验报告 实验名称 实验三 自下而上语法分析及语义分析 院 系 计算机科学和技术学院 专业年级 学生姓名 学号 指导老师 实验日期 实验三自上而下的语法分析 一实验目的 通过本实验掌握LR... -
ChartParsers.jl：Julia中无上下文语法的基本自上而下和自下而上的图表解析-源码
2021-02-04 06:20:02ChartParsers.jl：Julia中无上下文语法的基本自上而下和自下而上的图表解析 -
编译原理实验三 自下而上语法分析
2021-06-13 18:35:13（2）通过设计、编制、调试一个典型的自下而上语法分析程序，实现对语法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 （3）选择最有代表性的语法分析方法，算符优先分析法、LR...展开全文一、实验目的
（1）根据 PL/0 语言的文法规范，要求编写 PL/0语言的语法分析程序。
（2）通过设计、编制、调试一个典型的自下而上语法分析程序，实现对语法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。
（3）选择最有代表性的语法分析方法，算符优先分析法、LR分析法；或者调研语法分析器的自动生成工具YACC的功能与工作原理，使用YACC生成一个自底向上的语法分析器。二、实验内容
（1）已给 PL/0 语言文法，构造表达式部分的语法分析器。
分析对象〈算术表达式〉的 BNF 定义如下：
<表达式> ::= [+|-]<项>{<加法运算符> <项>}
<项> ::= <因子>{<乘法运算符> <因子>}
<因子> ::= <标识符>| <无符号整数> | ‘(’<表达式>‘)’
<加法运算符> ::= +|-
<乘法运算符> ::= *|/巴科斯范式(BNF)的语法规则：
在双引号中的字(“word”)代表着这些字符本身。而double_quote用来代表双引号。
在双引号外的字（有可能有下划线）代表着语法部分。
尖括号( < > )内包含的为必选项。
方括号( [ ] )内包含的为可选项。
大括号( { } )内包含的为可重复0至无数次的项。
竖线( | )表示在其左右两边任选一项，相当于"OR"的意思。
::= 是“被定义为”的意思。(2)根据实验一的词法分析的结果进行输入。例如：对于 PL/0 表达式，（a+15）*b 用下列形式作为输入：
(lparen,( )
(ident, a)
(plus, + )
(number, 15)
(rparen,) )
(times, * )
(ident, b )
输出：
对于语法正确的表达式，输出为“Yes,it is correct.”
对于语法错误的表达式，输出为“No,it is wrong.”三、设计思想及实验步骤
（一）设计思想
本实验采用算符优先分析法。算符优先分析是定义在算符之间的某种优先关系，借助于这种优先关系寻找可规约串和进行规约。对于文法G：
<表达式> ::= [+|-]<项>{<加法运算符> <项>}
<项> ::= <因子>{<乘法运算符> <因子>}
<因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
<关系运算符> ::= =|#|<|<=|>|>=可以改写如下所示：
S’-><表达式>
<表达式>-><项>
<表达式>-><表达式>+<项>
<表达式>-><表达式>-<项>
<项>-><因子>
<项>-><项>*<因子>
<项>-><项>/<因子>
<因子>->(<表达式>)
<因子>-><标识符>
<因子>-><无符号整数>算符文法的定义：
一个文法，如果它的任一产生式的右部都不含两个相继并列的非终结符，如设有一个文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法。
对于优先关系进行如下定义：
a的优先级小于b
(1) a<b： 当且仅当文法G中有形如P→…aR…的产生式而R⇒+b…或R⇒+Qb…
a的优先级等于b
(2) a=b：当且仅当文法G中有形如P→…ab…或者P→…aQb…的产生式
a的优先级高于b
(3) a>b：当且仅当文法G中有形如P→…Rb…的产生式,而R⇒+…a或R⇒+…aR
如果一个算符文法G中的任何终结符对（a，b）至多满足下述三关系之一：a<b,a=b,a>b，则称G是一个算符优先文法。从算符优先文法G构造优先关系表：
检查G的每个产生式的每个候选式，可找出所有满足a=b的终结符对，为找出所有满足关系<和>的终结符对，需要对G的每个非终结符P构造两个集合FIRSTVT§和LASTVT§。
定义并构造FIRSTVT和LASTVT两个集合
FIRSTVT§={a|P⇒+a⋯或P⇒+Qa⋯}
LASTVT§={a|P⇒+⋯a或P⇒+⋯aQ}（二）实验步骤
（1）构造文法G的FIRSTVT集和LASTVT集
文法：
B -> J X(J X)* | X (J X)* （表达式）
X ->Y (C Y)* （项）
Y ->I | N |( B ) （因子）
J -> + | - （加法运算符）
C -> * | / （乘法运算符）FIRSTVT集:
FIRSTVT(表达式)={+，-，(,， /，标识符，无符号整数 }
FIRSTVT(项)={，/，（，标识符，无符号整数}
FIRSTVT(因子)={(，标识符，无符号整数}
FRTSTVT(加法运算符)={+，-}
FRTSTVT(乘法运算符)={，/}LASTVT集:
LASTVT(表达式)={+，-,），， /，标识符，无符号整数 }
LASTVT(项)={，/，)，标识符，无符号整数}
LASTVT(因子)={)，标识符，无符号整数}（2）构造优先关系表
（3）构造总控程序
算法优先分析算法描述如下：
stack S;
k = 1; //符号栈S的使用深度
S[k] = ‘#’
REPEAT
把下一个输入符号读进a中；
If S[k]∈ VT then j = k else j = k-1;
While S[j] > a do
Begin
Repeat
Q = S[j];
if S[j-1] VT then j = j-1 else j = j-2
until S[j] < Q;
把S[j+1]…S[k]归约为某个N，并输出归约为哪个符号；
K = j+1;
S[k] = N;
end of while
if S[j] < a or S[j] = a then
begin k = k+1; S[k] = a end
else error //调用出错诊察程序
until a = ‘#’算法解释说明：a中存放的是目前分析到的句子中的终结符,不断比较栈顶的首终结符s[j]与a中的终结符的优先级。若s[j]优先级低于a或与a相同，则a中 终结符进栈；若s[j]优先级高于a， 则在栈中向下找，直到找到优先级比s[j] 低的终结符，假设用b表示，然后将栈中b之上的串（就是最左素短语）归约到N（弹出栈中b之上的串，N入栈），此时栈顶首终结符b就是新的s[j]，接着比较栈顶首终结 符s[j]和a的优先级，重复以上步骤。
（4）算法流程图
四、源程序及调试运行结果
1.源程序代码：
#include <iostream> #include<bits/stdc++.h> //万能头文件 using namespace std; #define M 9 // 算符优先关系表 int findP(int a, int b) // a、b ∈ [1,9]，从1开始 { int table[M][M] = // 1表示优先级高于，-1表示优先级低于，0表示优先级等于，2表示空 { {0,0,-1,-1,-1,-1,-1,1,1}, {0,0,-1,-1,-1,-1,-1,1,1}, {1,1,0,0,-1,-1,-1,1,1}, {1,1,0,0,-1,-1,-1,1,1}, {1,1,1,1,0,2,2,1,1}, {1,1,1,1,2,0,2,1,1}, {-1,-1,-1,-1,-1,-1,-1,0,1}, {1,1,1,1,2,2,0,1,1}, {-1,-1,-1,-1,-1,-1,-1,-1,0} }; return table[a-1][b-1]; //数组下标从0开始 } // 判断c是否终结符，不是返回0，是返回它在优先关系表中的行号（从1开始） int Is_Vt(char c) { int n; switch(c) { case 'p': n=1; break; //plus + case 'm': n=2; break;//minus - case 't': n=3; break;//times * case 's': n=4; Break;//slash / case 'i': n=5; break;//ident case 'n': n=6; break;//number case 'l': n=7; break;//lparen （ case 'r': n=8; break;//rparen ） case '#': n=9; break; default: n=0; } return n; } void Getinputs(char* inputs)//输入 { int i = 0; string line; while(cin >> line) { inputs[i++] = line[1]; } inputs[i] = '#'; } // 判断表达式的合法性，p指向分析栈的首部，k指向栈顶；psc指向当前输入符号 int judge(char* p, int k, char* psc) { //当前输入符号为运算符，而栈顶为#，运算符前面没有操作数 if(k == 1 && p[k] == '#' && (*psc == 'p' || *psc == 'm' || *psc == 't' || *psc == 's')) { return 0; } //当前输入符号为#，上一个输入符号为运算符，运算符后面没有操作数 if(*psc == '#' && (*(psc-1) == 'p' || *(psc-1) == 'm' || *(psc-1) == 't' || *(psc-1) == 's')) { return 0; } //运算符号相邻 if(((*psc == 'p' || *psc == 'm' || *psc == 't' || *psc == 's') && ((*(psc+1) == 'p' || *(psc+1) == 'm' || *(psc+1) == 't' || *(psc+1) == 's')))) { return 0; } return 1; } int main() { char s[30] = {'\0'};//分析栈s int k = 1; // k指向栈顶 s[k] = '#'; s[k+1] = '\0'; int j; // j指向栈顶的终结符 char q; // q表示j指向的元素，即栈顶终结符 // 输入处理 char inputs[100] = {'\0'}; // 输入串 Getinputs(inputs); //printf("字符串是：%s\n", inputs); char *psc = inputs; // 指向当前输入符号 int flag; // 查算符优先关系表得到的值（1/-1/0/2）(大于/小于/等于/空) // 算符优先分析算法总控程序 while(1) { if(!judge(s, k, psc)) //表达式不合法，直接报错 { printf("No,it is wrong."); exit(1); } // 让j指向栈顶终结符 if(Is_Vt(s[k])) j = k; else j = k-1; // 比较s[j]和*psc(当前输入符号）的优先关系，判断移进还是规约 flag = findP(Is_Vt(s[j]), Is_Vt(*psc)); if(flag == 1) // s[j] 优先级高于 *psc，进行规约 { //在栈顶中向下找，直到找到优先级低于s[j]的终结符 do { q = s[j];// q保存当前的终结符 // j向下探一（两）步，找到下一个终结符 if(Is_Vt(s[j-1])) j--; else j-=2; } while(findP(Is_Vt(s[j]), Is_Vt(q)) != -1); k = j+1; s[k] = 'N'; // 将栈中q以上（不包括q)的串归约到N s[k+1] = '\0'; continue; } else if(flag == -1) // s[j] 优先级低于*psc，移进 { k++; s[k] = *psc; s[k+1] = '\0'; psc++; continue; } else if(flag == 0) { if(s[j] == '#') { printf("Yes,it is correct."); break; } else // 否则移进 { k++; s[k] = *psc; s[k+1] = '\0'; psc++; continue; } } else // 优先关系表中为空的地方 { printf("No,it is wrong."); exit(1); } } return 0; }2.程序运行结果截图
测试数据一：
测试数据二：
-
笔记-编译原理-实验三-自下而上语法分析-SLR分析法
2020-05-06 12:54:30根据对自下而上语法分析的理论知识的学习，可以知道自下而上语法分析的两种实现方法：算符优先分析法和LR分析法，本实验采用后者LR分析法 本实验对PL0文法的表达式文法进行设计自下而上语法分析，表达式巴斯克范式...展开全文实验三. 自上而下语法分析 设计思想
根据对自下而上语法分析的理论知识的学习，可以知道自下而上语法分析的两种实现方法：算符优先分析法和LR分析法，本实验采用后者LR分析法
本实验对PL0文法的表达式文法进行设计自下而上语法分析，表达式巴斯克范式如下：
文法的初始化
< 表 达 式 > : : = [ + ∣ − ] < 项 > { < 加 法 运 算 符 > < 项 > } < 项 > : : = < 因 子 > { < 乘 法 运 算 符 > < 因 子 > } < 因 子 > : : = < 标 识 符 > ∣ < 无 符 号 整 数 > ∣ ′ ( ′ < 表 达 式 > ′ ) ′ < 加 法 运 算 符 > : : = + ∣ − < 乘 法 运 算 符 > : : = ∗ ∣ / \begin{aligned} & <表达式> ::= [+|-]<项>\{<加法运算符> <项>\} \\ & <项> ::= <因子>\{<乘法运算符> <因子>\} \\ & <因子> ::= <标识符>|<无符号整数>| '('<表达式>')' \\ & <加法运算符> ::= +|- \\ & <乘法运算符> ::= *|/ \end{aligned} <表达式>::=[+∣−]<项>{<加法运算符><项>}<项>::=<因子>{<乘法运算符><因子>}<因子>::=<标识符>∣<无符号整数>∣′(′<表达式>′)′<加法运算符>::=+∣−<乘法运算符>::=∗∣/
对以上文字描述的文法可以给出对应的英文表示，以及对应的非终结符的 F i r s t 集 合 First集合 First集合 和 F o l l o w 集 合 Follow集合 Follow集合 ：
< E x p r e s s i o n > : : = [ + ∣ − ] < T e r m > { < A d d o p > < T e r m > } < T e r m > : : = < F a c t o r > { < M u l o p > < F a c t o r > } < F a c t o r > : : = < I d e n t > ∣ < U n s i g n I n t > ∣ ( < E x p r e s s i o n > ) < A d d o p > : : = + ∣ − < M u l o p > : : = ∗ ∣ / \begin{aligned} & <Expression> ::= [+|-]<Term>\{<Addop> <Term>\} \\ & <Term> ::= <Factor>\{<Mulop> <Factor>\} \\ & <Factor> ::= <Ident> | <UnsignInt> | (<Expression>) \\ & <Addop> ::= + | - \\ & <Mulop> ::= * | / \\ \end{aligned} <Expression>::=[+∣−]<Term>{<Addop><Term>}<Term>::=<Factor>{<Mulop><Factor>}<Factor>::=<Ident>∣<UnsignInt>∣(<Expression>)<Addop>::=+∣−<Mulop>::=∗∣/
该文法的非终结符结合以及终结符集合如下：
V T = { + , − , ∗ , / , ( , ) , I d e n t , U n s i g n I n t } V N = { E x p r e s s i o n , T e r m , A d d o p , F a c t o r , M u l o p } \begin{aligned} & V_T = \{+, -, *, /, (, ), Ident, UnsignInt\} \\ & V_N = \{Expression, Term, Addop, Factor, Mulop\} \\ \end{aligned} VT={+,−,∗,/,(,),Ident,UnsignInt}VN={Expression,Term,Addop,Factor,Mulop}F i r s t 集 合 First集合 First集合 :
F i r s t ( E x p r e s s i o n ) = { + , − , I d e n t , U n s i g n I n t , ( } F i r s t ( T e r m ) = { I d e n t , U n s i g n I n t , ( } F i r s t ( F a c t o r ) = { I d e n t , U n s i g n I n t , ( } F i r s t ( A d d o p ) = { + , − } F i r s t ( M u l o p ) = { ∗ , / } \begin{aligned} & First(Expression) = \{+, -, Ident, UnsignInt, (\} \\ & First(Term) = \{Ident, UnsignInt, (\} \\ & First(Factor) = \{Ident, UnsignInt, (\} \\ & First(Addop) = \{+, -\} \\ & First(Mulop) = \{*, /\} \\ \end{aligned} First(Expression)={+,−,Ident,UnsignInt,(}First(Term)={Ident,UnsignInt,(}First(Factor)={Ident,UnsignInt,(}First(Addop)={+,−}First(Mulop)={∗,/}
F o l l o w 集 合 Follow集合 Follow集合 :
F o l l o w ( S ′ ) = { # } F o l l o w ( E x p r e s s i o n ) = { # , + , − , ) } F o l l o w ( T e r m ) = { # , + , − , ∗ , / , ) } F o l l o w ( F a c t o r ) = { # , + , − , ∗ , / , ) } \begin{aligned} & Follow(S') = \{\#\} \\ & Follow(Expression) = \{\#, +, -, )\} \\ & Follow(Term) = \{\#, +, -, *, /, )\} \\ & Follow(Factor) = \{\#, +, -, *, /, )\} \\ \end{aligned} Follow(S′)={#}Follow(Expression)={#,+,−,)}Follow(Term)={#,+,−,∗,/,)}Follow(Factor)={#,+,−,∗,/,)}
将其简化一下文法：
E → T ∣ + T ∣ − T E → E + T ∣ E − T T → F T → T ∗ F ∣ T / F F → i ∣ u ∣ ( E ) \begin{aligned} E & \to T | +T | -T \\ E & \to E + T | E - T\\ T & \to F \\ T & \to T * F | T / F \\ F & \to i | u | (E) \\ \end{aligned} EETTF→T∣+T∣−T→E+T∣E−T→F→T∗F∣T/F→i∣u∣(E)
对应的终结符和非终结符集合如下：
V T = { + , − , ∗ , / , ( , ) , i , u } V N = { S ′ , E , T , F } \begin{aligned} & V_T = \{+, -, *, /, (, ), i, u\} \\ & V_N = \{S', E, T, F\} \end{aligned} VT={+,−,∗,/,(,),i,u}VN={S′,E,T,F}
拓广文法
文法的拓广，将文法 G ( S ) G(S) G(S) 拓广为 G ′ ( S ′ ) G'(S') G′(S′) ，并规定每一个产生式的编号，以便后续的方便使用：
0 : S ′ → E 1 : E → T 2 : E → + T 3 : E → − T 4 : E → E + T 5 : E → E − T 6 : T → F 7 : T → T ∗ F 8 : T → T / F 9 : F → i 10 : F → u 11 : F → ( E ) \begin{aligned} & 0: & S &' \to E \\ & 1: & E & \to T \\ & 2: & E & \to +T \\ & 3: & E & \to -T \\ & 4: & E & \to E + T \\ & 5: & E & \to E - T \\ & 6: & T & \to F \\ & 7: & T & \to T * F \\ & 8: & T & \to T / F \\ & 9: & F & \to i \\ & 10: & F & \to u \\ & 11: & F & \to (E) \\ \end{aligned} 0:1:2:3:4:5:6:7:8:9:10:11:SEEEEETTTFFF′→E→T→+T→−T→E+T→E−T→F→T∗F→T/F→i→u→(E)
构造识别活前缀的DFA
由此DFA可以看出，某些状态存在“规约-移进”冲突，所以可以通过SLR分析法的方式来尝试构造分析表，构造出此时构造出的分析表显然没有冲突：
SLR分析表
+ − ∗ / ( ) i u # E T F 0 s 5 s 4 s 8 s 6 s 7 1 2 3 1 s 9 s 10 a c c 2 r 1 r 1 s 11 s 12 r 1 r 1 3 r 6 r 6 r 6 r 6 r 6 r 6 4 13 5 14 6 r 9 r 9 r 9 r 9 r 9 r 9 7 r 10 r 10 r 10 r 10 r 10 r 10 8 s 5 s 4 s 8 s 6 s 7 15 2 3 9 s 8 s 6 s 7 16 3 10 s 8 s 6 s 7 17 3 11 s 8 s 6 s 7 18 12 s 8 s 6 s 7 19 13 r 3 r 3 r 3 r 3 14 r 2 r 2 r 2 r 2 15 s 9 s 10 s 20 16 r 4 r 4 s 11 s 12 r 4 r 4 17 r 5 r 5 s 11 s 12 r 5 r 5 18 r 7 r 7 r 7 r 7 r 7 r 7 19 r 8 r 8 r 8 r 8 r 8 r 8 20 r 11 r 11 r 11 r 11 r 11 r 11 \begin{array}{c|c} \hline & + & - & * & / & ( & ) & i & u & \# & E & T & F \\ \hline 0 & s5 & s4 & & & s8 & & s6 & s7 & & 1 & 2 & 3 \\ \hline 1 & s9 & s10 & & & & & & & acc & & & \\ \hline 2 & r1 & r1 & s11 & s12 & & r1 & & & r1 & & & \\ \hline 3 & r6 & r6 & r6 & r6 & & r6 & & & r6 & & & \\ \hline 4 & & & & & & & & & & & 13 & \\ \hline 5 & & & & & & & & & & & 14 & \\ \hline 6 & r9 & r9 & r9 & r9 & & r9 & & & r9 & & & \\ \hline 7 & r10 & r10 & r10 & r10 & & r10 & & & r10 & & & \\ \hline 8 & s5 & s4 & & & s8 & & s6 & s7 & & 15 & 2 & 3 \\ \hline 9 & & & & & s8 & & s6 & s7 & & & 16 & 3 \\ \hline 10 & & & & & s8 & & s6 & s7 & & & 17 & 3 \\ \hline 11 & & & & & s8 & & s6 & s7 & & & & 18 \\ \hline 12 & & & & & s8 & & s6 & s7 & & & & 19 \\ \hline 13 & r3 & r3 & & & & r3 & & & r3 & & & \\ \hline 14 & r2 & r2 & & & & r2 & & & r2 & & & \\ \hline 15 & s9 & s10 & & & & s20 & & & & & & \\ \hline 16 & r4 & r4 & s11 & s12 & & r4 & & & r4 & & & \\ \hline 17 & r5 & r5 & s11 & s12 & & r5 & & & r5 & & & \\ \hline 18 & r7 & r7 & r7 & r7 & & r7 & & & r7 & & & \\ \hline 19 & r8 & r8 & r8 & r8 & & r8 & & & r8 & & & \\ \hline 20 & r11 & r11 & r11 & r11 & & r11 & & & r11 & & & \\ \hline \end{array} 01234567891011121314151617181920+s5s9r1r6r9r10s5r3r2s9r4r5r7r8r11−s4s10r1r6r9r10s4r3r2s10r4r5r7r8r11∗s11r6r9r10s11s11r7r8r11/s12r6r9r10s12s12r7r8r11(s8s8s8s8s8s8)r1r6r9r10r3r2s20r4r5r7r8r11is6s6s6s6s6s6us7s7s7s7s7s7#accr1r6r9r10r3r2r4r5r7r8r11E115T2131421617F33331819
得到分析表后，就可以根据LR分析的程序框架完成总控程序等的编写，由上一次的 自上而下的SLR分析表法 的代码可以简单的修改一些代码，便可实现整个分析程序的编写。
算法流程
源程序
整个SLR分析程序是由上一实验的预测分析程序修改而来，根据SLR分析的所需，简单的修改了分析表的构成，即由ACTION和GOTO表组成，将原来的分析总控程序中的具体的执行流程根据LR分析法来修改，其他内容保持不变即可：
整个LR分析程序所设计到的类以及相互的关系如下：
基础符号类
基础符号类作为一个符号类的基类，主要用途为使用基类指针来指引子类的终结符或非终结符，简化后续的操作。
// symbols.h #ifndef symbols_h #define symbols_h #include<iostream> /* 终结符和非终结符的一个共同的基类 这样可以通过基类来引用终结符和非终结符 */ class symbols { private: /* data */ public: symbols(){}; virtual ~symbols(){}; virtual std::string getClassName(){ return "symbols"; } virtual void print(){}; }; #endif /*symbols_h*/终结符类
终结符类继承至基础符号类，终结符由终结符的值和编码构成。
// symbolsVT.h #ifndef symbolsVT_h #define symbolsVT_h #include<iostream> #include"symbols.h" /* 一个终结符 终结符由终结符的值和编码构成 */ class symbolsVT : public symbols{ private: std::string word; //终结符的值 std::string code; //词法分析后终结符的标识（编码） public: symbolsVT(){} symbolsVT(std::string W, std::string C):word(W), code(C) { std::cerr<< "V_T: " << word << " " << code << " created..." << std::endl; } ~symbolsVT() {} std::string getClassName(); std::string getWord(); std::string getCode(); void print(); }; #endif /*symbolsVT_h*/// symbolsVT.cpp #include<iostream> #include"symbolsVT.h" std::string symbolsVT::getClassName(){ return "VT"; } std::string symbolsVT::getWord(){ return word; } std::string symbolsVT::getCode(){ return code; } void symbolsVT::print(){ std::cerr << "VT: " << word << " " << code << std::endl; }非终结符类
非终结符类与终结符类一样继承至基础符号类，非终结符由其左部的非终结符和有部一个一些产生式构成，产生式即为一些符号的排列，此处存储的是一些产生式的指针。
// symbolsVN.h #ifndef symbolsVN_h #define symbolsVN_h #include<iostream> #include"symbols.h" #include"production.h" const int maxnNum = 5; // 一个终结符所有的产生式的数量 class production; /* 非终结符 非终结符由其左部的非终结符和有部一个一些产生式构成 产生式即为一些符号的排列，此处存储的是一些产生式的指针 */ class symbolsVN: public symbols{ private: std::string name; // 非终结符左部名称X production *p[maxnNum]; // 产生式集合 int num; public: symbolsVN(); symbolsVN(std::string); ~symbolsVN() {} std::string getClassName(); std::string getName(); void insertProduction(production *newp); // 加入一个产生式 production* getProductionIndexOf(int i); // 获得第i个产生式 production** getAllProduction(); // 获得所有的产生式 void print(); }; #endif /*symbolsVN_h*/// symbolsVN.cpp #include<iostream> #include"symbolsVN.h" symbolsVN::symbolsVN(){ num = 0; } symbolsVN::symbolsVN(std::string n):name(n){ symbolsVN(); std::cerr << "V_N: " << name << " created..." << std::endl; } std::string symbolsVN::getClassName(){ return "VN"; } std::string symbolsVN::getName(){ return name; } void symbolsVN::insertProduction(production *newp){ p[num++] = newp; return; } production* symbolsVN::getProductionIndexOf(int i){ if(i >= num){ std::cerr << "index overflow..." << std::endl; return NULL; } return p[i]; } production** symbolsVN::getAllProduction(){ return p; } void symbolsVN::print(){ std::cerr << "VN: " << name << std::endl; std::cerr << "ALL production: " << std::endl; for(int i = 0; i < num; ++i){ std::cerr << name << " \\to "; p[i]->print(); } std::cerr << std::endl; }产生式类
一个产生式由一个左部的非终结符和一些右部的符号集合构成。
// production.h #ifndef production_h #define production_h #include<iostream> #include"symbols.h" #include"symbolsVT.h" #include"symbolsVN.h" /* 产生式 一个产生式由一个左部的非终结符和一些右部的符号集合构成 */ const int maxnLen = 10; // 一个产生式的右部符号的数量 class symbolsVN; class production { private: symbolsVN *vn; // 产生式左部的非终结符 symbols *pro[maxnLen]; // 产生式，由一些非终结符和终结符构成，故使用符号指针来指引 int len; public: production(); production(symbolsVN *v); ~production(){} void push_back(symbols *a); // 为产生式后部插入一个符号 symbolsVN* getVN(); // 获得左部非终结符符号 symbols** getProduction(); // 获得产生式指针数组 int getLen(); // 获得产生式长度 symbols* getProductionIndexOf(int i); // 获得产生式中第i个位置的符号 void print(); }; #endif /*production_h*/// production.cpp #include<iostream> #include"production.h" #include"symbolsVT.h" #include"symbolsVN.h" production::production(){ len = 0; } production::production(symbolsVN *v){ vn = v; production(); std::cerr << "A production of " << vn->getName() << " has created..." << std::endl; } void production::push_back(symbols *a){ pro[len++] = a; } symbolsVN* production::getVN(){ return vn; } symbols** production::getProduction(){ return pro; } symbols* production::getProductionIndexOf(int i){ if(i >= len){ std::cerr << "index Overflow..." << std::endl; return NULL; } return pro[i]; } int production::getLen(){ return len; } void production::print(){ std::cerr << vn->getName() << "->"; for(int i = 0; i < len; ++i){ if(pro[i]->getClassName() == "VT"){ std::cerr << ((symbolsVT*)pro[i])->getWord(); } else{ std::cerr << ((symbolsVN*)pro[i])->getName(); } } // std::cerr << std::endl; }分析表
分析表，由ACTION表和GOTO表构成，具体的状态内容由前期的DFA分析等得到：
// analysisTable.h #ifndef analysisTable_h #define analysisTable_h #include<map> #include"symbols.h" #include"symbolsVN.h" #include"symbolsVT.h" #include"production.h" const int NUMOFVT = 20; const int NUMOFVN = 20; const int NUMOFSTATE = 30; const int NUMOFPRODUCTIONS = 30; /* 分析表子程序 由前期的分析得到该文法的分析表，由ACTION表和GOTO表构成 */ class ACTIONTable{ private: std::pair<char, int> ACTION[NUMOFSTATE][NUMOFVT]; int numofstate; // ACTION表状态的数量 int numofsymbolsvt; // ACTION表终结符的数量 std::map<symbolsVT*, int> vtmap; // 终结符对应在分析表中的位置 int getVTMap(symbolsVT*); // 获得终结符对应的编号 public: ACTIONTable(); ACTIONTable(int); ~ACTIONTable(){} void setNumOfState(int); // GOTO状态数量 void insertVT(symbolsVT*); // 插入一个终结符以及给一个对应的编号 void insertSHIFT(int state, symbolsVT* vt, int numOfPro); // 插入一个移进状态 void insertREDUCE(int state, symbolsVT* vt, int numOfPro); // 插入一个规约状态 void insertACC(int state, symbolsVT* vt); // 插入一个acc状态 std::pair<char, int> getACTION(int state, symbolsVT* vt); // 获得一个ACTION信息 void print(); }; class GOTOTable{ private: int GOTO[NUMOFSTATE][NUMOFVN]; int numofstate; // GOTO状态数量 int numofsymbolsvn; std::map<symbolsVN*, int> vnmap; // 非终结符对应在分析表中的位置 int getVNMap(symbolsVN*); // 获得非终结符对应的编号 public: GOTOTable(); GOTOTable(int); ~GOTOTable(){} void setNumOfState(int); // 设置GOTO表的状态数 void insertVN(symbolsVN*); // 插入一个非终结符 void insert(int state, symbolsVN* vn, int numOfPro); // 插入一个GOTO状态 int get(int state, symbolsVN* vn); // 获得一个GOTO状态 void print(); }; class analysisTable { private: ACTIONTable ACTION; // ACTION表 GOTOTable GOTO; // GOTO表 int numofstate; // 状态个数I_n int numofpro; // 产生式数量 production* productions[NUMOFPRODUCTIONS]; // 产生式数组，下标即为编号 public: analysisTable(int ns); // analysisTable(int, int, int); ~analysisTable() {} void insertSymbols(symbols*); // 插入一个符号 void insertProduction(production* p); // 插入一条产生式，自动编号 production* getProduction(int i); // 获得第i条产生式 void insert(int state, symbols* s, char ch, int numOfPro); // 插入一个状态 std::pair<char, int> get(int state, symbols* s); // 获得一个状态 void print(); }; #endif /*analysisTable_h*/// analysisTable.cpp #include<iostream> #include<algorithm> #include<string.h> #include"analysisTable.h" ACTIONTable::ACTIONTable(){ numofsymbolsvt = 0; vtmap.clear(); std::pair<char, int> init = std::make_pair('e', -1); // fill(begin(ACTION), end(ACTION), std::make_pair('e', -1)); for(int i = 0; i < NUMOFSTATE; ++i) for(int j = 0; j < NUMOFVT; ++j) ACTION[i][j] = init; std::cerr << "ACTIONTable has created..." << std::endl; } void ACTIONTable::setNumOfState(int ns){ numofstate = ns; } int ACTIONTable::getVTMap(symbolsVT* vt){ if(vtmap.find(vt) != vtmap.end())return vtmap[vt]; return -1; } void ACTIONTable::insertVT(symbolsVT* vt){ vtmap[vt] = numofsymbolsvt++; } void ACTIONTable::insertSHIFT(int state, symbolsVT* vt, int numOfPro){ int nvt = getVTMap(vt); if(state < numofstate && ~nvt){ ACTION[state][nvt] = std::make_pair('s', numOfPro); } } void ACTIONTable::insertREDUCE(int state, symbolsVT* vt, int numOfPro){ int nvt = getVTMap(vt); if(state < numofstate && ~nvt){ ACTION[state][nvt] = std::make_pair('r', numOfPro); } } void ACTIONTable::insertACC(int state, symbolsVT* vt){ int nvt = getVTMap(vt); if(state < numofstate && ~nvt){ ACTION[state][nvt] = std::make_pair('a', 0x3f3f3f3f); } } std::pair<char, int> ACTIONTable::getACTION(int state, symbolsVT* vt){ int nvt = getVTMap(vt); if(state < numofstate && ~nvt){ return ACTION[state][nvt]; } return std::make_pair('e', -1); } void ACTIONTable::print(){ std::cerr << "ACTION:" << std::endl; std::cerr << numofsymbolsvt << std::endl; std::cerr << "\t"; // for(auto i: vtmap)std::cerr << i.first->getWord() << "\t"; for(std::map<symbolsVT*, int>::iterator i = vtmap.begin(); i != vtmap.end(); ++i)std::cerr << i->first->getWord() << "\t"; std::cerr << std::endl; for(int i = 0; i < numofstate; ++i){ std::cerr << i << ": \t"; for(int j = 0; j < numofsymbolsvt; ++j){ if(~ACTION[i][j].second) std::cerr << ACTION[i][j].first << ACTION[i][j].second << " \t"; else std::cerr << " \t"; } std::cerr << std::endl; } std::cerr << std::endl; } GOTOTable::GOTOTable(){ numofsymbolsvn = 0; vnmap.clear(); memset(GOTO, -1, sizeof GOTO); std::cerr << "GOTOTable has created..." << std::endl; } void GOTOTable::setNumOfState(int ns){ numofstate = ns; } void GOTOTable::insertVN(symbolsVN* vn){ vnmap[vn] = numofsymbolsvn++; } int GOTOTable::getVNMap(symbolsVN* vn){ if(vnmap.find(vn) != vnmap.end())return vnmap[vn]; return -1; } void GOTOTable::insert(int state, symbolsVN* vn, int numOfPro){ int nvn = getVNMap(vn); if(state < numofstate && ~nvn){ GOTO[state][nvn] = numOfPro; } } int GOTOTable::get(int state, symbolsVN* vn){ int nvn = getVNMap(vn); if(state < numofstate && ~nvn){ return GOTO[state][nvn]; } return -1; } void GOTOTable::print(){ std::cerr << "GOTO:" << std::endl; std::cerr << numofsymbolsvn << std::endl; std::cerr << "\t"; // for(auto i: vnmap)std::cerr << i.first->getName() << "\t"; for(std::map<symbolsVN*, int>::iterator i = vnmap.begin(); i != vnmap.end(); ++i)std::cerr << i->first->getName() << "\t"; std::cerr << std::endl; for(int i = 0; i < numofstate; ++i){ std::cerr << i << ": \t"; for(int j = 0; j < numofsymbolsvn; ++j){ if(~GOTO[i][j]) std::cerr << GOTO[i][j] << "\t"; else std::cerr << " \t"; } std::cerr << std::endl; } std::cerr << std::endl; } analysisTable::analysisTable(int ns):numofstate(ns){ ACTION.setNumOfState(numofstate); GOTO.setNumOfState(numofstate); numofpro = 0; std::cerr << "An AnalysisTable has created..." << std::endl; } void analysisTable::insertSymbols(symbols* s){ if(s->getClassName() == "VT"){ ACTION.insertVT((symbolsVT*)(s)); } else if(s->getClassName() == "VN"){ GOTO.insertVN((symbolsVN*)(s)); } } void analysisTable::insertProduction(production* p){ productions[numofpro++] = p; } production* analysisTable::getProduction(int i){ if(i < numofpro)return productions[i]; // return nullptr; return NULL; } void analysisTable::insert(int state, symbols* s, char ch, int numOfPro){ if(s->getClassName() == "VT"){ if(ch == 'a'){ ACTION.insertACC(state, (symbolsVT*)(s)); } else if(ch == 's'){ ACTION.insertSHIFT(state, (symbolsVT*)(s), numOfPro); } else if(ch == 'r'){ ACTION.insertREDUCE(state, (symbolsVT*)(s), numOfPro); } } else if(s->getClassName() == "VN"){ GOTO.insert(state, (symbolsVN*)(s), numOfPro); } } std::pair<char, int> analysisTable::get(int state, symbols* s){ if(s->getClassName() == "VT"){ return ACTION.getACTION(state, (symbolsVT*)(s)); } else if(s->getClassName() == "VN"){ return std::make_pair('g', GOTO.get(state, (symbolsVN*)(s))); } return std::make_pair('e', -1); } void analysisTable::print(){ std::cerr << "analysisTable: " << std::endl; ACTION.print(); GOTO.print(); std::cerr << std::endl; }LR分析总控程序
根据LR分析程序编写的总控程序，包括初始化、读入、分析以及释放资源等：
// SLRAnalysis.cpp #include<iostream> #include<cstdio> #include<string.h> #include"symbols.h" #include"symbolsVN.cpp" #include"symbolsVT.cpp" #include"production.cpp" #include"analysisTable.cpp" const int maxnAnalysisStack = 1e2 + 5; // 定义出文法的所有终结符 symbolsVT* PLUS = new symbolsVT("+", "plus"); symbolsVT* MINUS = new symbolsVT("-", "minus"); symbolsVT* times = new symbolsVT("*", "times"); symbolsVT* slash = new symbolsVT("/", "slash"); symbolsVT* lparen = new symbolsVT("(", "lapren"); symbolsVT* rparen = new symbolsVT(")", "rparen"); symbolsVT* ident = new symbolsVT("i", "ident"); symbolsVT* unsignint = new symbolsVT("u", "unsignint"); symbolsVT* END = new symbolsVT("#", "end"); symbolsVT* epslion = new symbolsVT("e", "epslion"); // 定义出文法的所有非终结符 symbolsVN* Sdot = new symbolsVN("S'"); symbolsVN* E = new symbolsVN("E"); symbolsVN* T = new symbolsVN("T"); symbolsVN* F = new symbolsVN("F"); // 构造所有的产生式 production* Sdotproduction[1]; production* Eporduction[5]; production* Tproduction[3]; production* Fproduction[3]; // 定义出预测分析表 analysisTable AnalysisTable(21); // 分析栈 std::pair<int, symbols*> analysisStack[maxnAnalysisStack]; int top; void init(){ // 初始化所有变量 // 根据文法的不同，得到的分析表的结构也不同，此时初始化部分也不同 // 定义出预测分析表 // 为预测分析表插入终结符、非终结符 AnalysisTable.insertSymbols(PLUS); AnalysisTable.insertSymbols(MINUS); AnalysisTable.insertSymbols(times); AnalysisTable.insertSymbols(slash); AnalysisTable.insertSymbols(lparen); AnalysisTable.insertSymbols(rparen); AnalysisTable.insertSymbols(ident); AnalysisTable.insertSymbols(unsignint); AnalysisTable.insertSymbols(END); AnalysisTable.insertSymbols(Sdot); AnalysisTable.insertSymbols(E); AnalysisTable.insertSymbols(T); AnalysisTable.insertSymbols(F); // 根据文法定义E的三条产生式，同理处理其他的产生式 for(int i = 0; i < 1; ++i)Sdotproduction[i] = new production(Sdot); Sdotproduction[0]->push_back(E); Sdotproduction[0]->print(); for(int i = 0; i < 5; ++i)Eporduction[i] = new production(E); Eporduction[0]->push_back(T); Eporduction[1]->push_back(PLUS); Eporduction[1]->push_back(T); Eporduction[2]->push_back(MINUS); Eporduction[2]->push_back(T); Eporduction[3]->push_back(E); Eporduction[3]->push_back(PLUS); Eporduction[3]->push_back(T); Eporduction[4]->push_back(E); Eporduction[4]->push_back(MINUS); Eporduction[4]->push_back(T); for(int i = 0; i < 5; ++i)E->insertProduction(Eporduction[i]); for(int i = 0; i < 5; ++i)Eporduction[i]->print(); for(int i = 0; i < 3; ++i)Tproduction[i] = new production(T); Tproduction[0]->push_back(F); Tproduction[1]->push_back(T); Tproduction[1]->push_back(times); Tproduction[1]->push_back(F); Tproduction[2]->push_back(T); Tproduction[2]->push_back(slash); Tproduction[2]->push_back(F); for(int i = 0; i < 3; ++i)T->insertProduction(Tproduction[i]); for(int i = 0; i < 3; ++i)Tproduction[i]->print(); for(int i = 0; i < 3; ++i)Fproduction[i] = new production(F); Fproduction[0]->push_back(ident); Fproduction[1]->push_back(unsignint); Fproduction[2]->push_back(lparen); Fproduction[2]->push_back(E); Fproduction[2]->push_back(rparen); for(int i = 0; i < 3; ++i)F->insertProduction(Fproduction[i]); for(int i = 0; i < 3; ++i)Fproduction[i]->print(); for(int i = 0; i < 1; ++i)AnalysisTable.insertProduction(Sdotproduction[i]); for(int i = 0; i < 5; ++i)AnalysisTable.insertProduction(Eporduction[i]); for(int i = 0; i < 3; ++i)AnalysisTable.insertProduction(Tproduction[i]); for(int i = 0; i < 3; ++i)AnalysisTable.insertProduction(Fproduction[i]); // 给出LR分析表 AnalysisTable.insert(0, PLUS, 's', 5); AnalysisTable.insert(0, MINUS, 's', 4); AnalysisTable.insert(0, lparen, 's', 8); AnalysisTable.insert(0, ident, 's', 6); AnalysisTable.insert(0, unsignint, 's', 7); AnalysisTable.insert(0, E, ' ', 1); AnalysisTable.insert(0, T, ' ', 2); AnalysisTable.insert(0, F, ' ', 3); AnalysisTable.insert(1, PLUS, 's', 9); AnalysisTable.insert(1, MINUS, 's', 10); AnalysisTable.insert(1, END, 'a', -1); AnalysisTable.insert(2, PLUS, 'r', 1); AnalysisTable.insert(2, MINUS, 'r', 1); AnalysisTable.insert(2, times, 's', 11); AnalysisTable.insert(2, slash, 's', 12); AnalysisTable.insert(2, rparen, 'r', 1); AnalysisTable.insert(2, END, 'r', 1); AnalysisTable.insert(3, PLUS, 'r', 6); AnalysisTable.insert(3, MINUS, 'r', 6); AnalysisTable.insert(3, times, 'r', 6); AnalysisTable.insert(3, slash, 'r', 6); AnalysisTable.insert(3, rparen, 'r', 6); AnalysisTable.insert(3, END, 'r', 6); AnalysisTable.insert(4, T, ' ', 13); AnalysisTable.insert(5, T, ' ', 14); AnalysisTable.insert(6, PLUS, 'r', 9); AnalysisTable.insert(6, MINUS, 'r', 9); AnalysisTable.insert(6, times, 'r', 9); AnalysisTable.insert(6, slash, 'r', 9); AnalysisTable.insert(6, rparen, 'r', 9); AnalysisTable.insert(6, END, 'r', 9); AnalysisTable.insert(7, PLUS, 'r', 10); AnalysisTable.insert(7, MINUS, 'r', 10); AnalysisTable.insert(7, times, 'r', 10); AnalysisTable.insert(7, slash, 'r', 10); AnalysisTable.insert(7, rparen, 'r', 10); AnalysisTable.insert(7, END, 'r', 10); AnalysisTable.insert(8, PLUS, 's', 5); AnalysisTable.insert(8, MINUS, 's', 4); AnalysisTable.insert(8, lparen, 's', 8); AnalysisTable.insert(8, ident, 's', 6); AnalysisTable.insert(8, unsignint, 's', 7); AnalysisTable.insert(8, E, ' ', 15); AnalysisTable.insert(8, T, ' ', 2); AnalysisTable.insert(8, F, ' ', 3); AnalysisTable.insert(9, lparen, 's', 8); AnalysisTable.insert(9, ident, 's', 6); AnalysisTable.insert(9, unsignint, 's', 7); AnalysisTable.insert(9, T, ' ', 16); AnalysisTable.insert(9, F, ' ', 3); AnalysisTable.insert(10, lparen, 's', 8); AnalysisTable.insert(10, ident, 's', 6); AnalysisTable.insert(10, unsignint, 's', 7); AnalysisTable.insert(10, T, ' ', 17); AnalysisTable.insert(10, F, ' ', 3); AnalysisTable.insert(11, lparen, 's', 8); AnalysisTable.insert(11, ident, 's', 6); AnalysisTable.insert(11, unsignint, 's', 7); AnalysisTable.insert(11, F, ' ', 18); AnalysisTable.insert(12, lparen, 's', 8); AnalysisTable.insert(12, ident, 's', 6); AnalysisTable.insert(12, unsignint, 's', 7); AnalysisTable.insert(12, F, ' ', 19); AnalysisTable.insert(13, PLUS, 'r', 3); AnalysisTable.insert(13, MINUS, 'r', 3); AnalysisTable.insert(13, rparen, 'r', 3); AnalysisTable.insert(13, END, 'r', 3); AnalysisTable.insert(14, PLUS, 'r', 2); AnalysisTable.insert(14, MINUS, 'r', 2); AnalysisTable.insert(14, rparen, 'r', 2); AnalysisTable.insert(14, END, 'r', 2); AnalysisTable.insert(15, PLUS, 's', 9); AnalysisTable.insert(15, MINUS, 's', 10); AnalysisTable.insert(15, rparen, 's', 20); AnalysisTable.insert(16, PLUS, 'r', 4); AnalysisTable.insert(16, MINUS, 'r', 4); AnalysisTable.insert(16, times, 's', 11); AnalysisTable.insert(16, slash, 's', 12); AnalysisTable.insert(16, rparen, 'r', 4); AnalysisTable.insert(16, END, 'r', 4); AnalysisTable.insert(17, PLUS, 'r', 5); AnalysisTable.insert(17, MINUS, 'r', 5); AnalysisTable.insert(17, times, 's', 11); AnalysisTable.insert(17, slash, 's', 12); AnalysisTable.insert(17, rparen, 'r', 5); AnalysisTable.insert(17, END, 'r', 5); AnalysisTable.insert(18, PLUS, 'r', 7); AnalysisTable.insert(18, MINUS, 'r', 7); AnalysisTable.insert(18, times, 'r', 7); AnalysisTable.insert(18, slash, 'r', 7); AnalysisTable.insert(18, rparen, 'r', 7); AnalysisTable.insert(18, END, 'r', 7); AnalysisTable.insert(19, PLUS, 'r', 8); AnalysisTable.insert(19, MINUS, 'r', 8); AnalysisTable.insert(19, times, 'r', 8); AnalysisTable.insert(19, slash, 'r', 8); AnalysisTable.insert(19, rparen, 'r', 8); AnalysisTable.insert(19, END, 'r', 8); AnalysisTable.insert(20, PLUS, 'r', 11); AnalysisTable.insert(20, MINUS, 'r', 11); AnalysisTable.insert(20, times, 'r', 11); AnalysisTable.insert(20, slash, 'r', 11); AnalysisTable.insert(20, rparen, 'r', 11); AnalysisTable.insert(20, END, 'r', 11); AnalysisTable.print(); // 初始化分析栈 top = -1; } void release(){ // 释放所有的动态申请的资源 delete PLUS; delete MINUS; delete times; delete slash; delete lparen; delete rparen; delete ident; delete unsignint; delete END; delete epslion; delete E; delete T; delete F; for(int i = 0; i < 1; ++i)delete Sdotproduction[i]; for(int i = 0; i < 5; ++i)delete Eporduction[i]; for(int i = 0; i < 3; ++i)delete Tproduction[i]; for(int i = 0; i < 3; ++i)delete Fproduction[i]; } std::string word, code; // char word[10], code[10]; char ch; symbolsVT* a; void ADVANCE(){ // 读入一个词法分析的结果项，同时给出对应的终结符a // if(scanf("(%s,%s)", code, word) != -1){ std::cin >> ch; if(!std::cin.eof()){ // if(scanf("%c", &ch) != -1){ std::getline(std::cin, code, ','); std::getline(std::cin, word); word.resize(word.size() - 1); // std::cin >> ch; std::cerr << word << " " << code << std::endl; if(code == "plus")a = PLUS; else if(code == "minus") a = MINUS; else if(code == "times") a = times; else if(code == "slash") a = slash; else if(code == "lparen") a = lparen; else if(code == "rparen") a = rparen; else if(code == "ident") a = ident; else if(code == "number") a = unsignint; } else{ a = END; // if(std::cin.eof() == EOF){ std::cerr << "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh" << std::endl; } std::cerr << word << "_____________" << code << std::endl; } bool SLRAnalysis(){ // 预测分析程序的总控程序 init(); bool grammer = true; // 表示句子是否符合一定的文法 bool flag = true; // 总控程序的运行标志 analysisStack[++top] = std::make_pair(0, (symbols*)END); // 初始化栈，将状态0和符号#压入 std::pair<int, symbols*> X; // 定义一个公共变量：状态和符号的指针 production *p; // 定义一个产生式的指针 std::pair<char, int> state; // 从分析表中获得的状态信息 ADVANCE(); // 读入一个词法分析的结果项 while(flag){ //************************************************************// // 调试信息：状态栈和符号栈的中内容 std::cerr << std::endl << std::endl; std::cerr << "================" << std::endl; a->print(); std::cerr << "stack: " << std::endl;; for(int i = 0; i <= top; ++i){ std::cerr << analysisStack[i].first << " "; } std::cerr << std::endl; for(int i = 0; i <= top; ++i){ if(analysisStack[i].second->getClassName() == "VT")std::cerr << ((symbolsVT*)(analysisStack[i].second))->getWord() << " "; else std::cerr << ((symbolsVN*)analysisStack[i].second)->getName() << " "; } std::cerr << std::endl << "================" << std::endl; std::cerr << std::endl; //************************************************************// X = analysisStack[top]; // 得到分析栈的栈顶元素，pop操作 state = AnalysisTable.get(X.first, a); // 根据栈顶的状态以及分析表中的变化情况来获得下一转换的状态s_i, r_i, acc, i等等 std::cerr << state.first << " " << state.second << std::endl; if(state.first == 's'){ // 如果是移进状态 analysisStack[++top] = std::make_pair(state.second, a); ADVANCE(); std::cerr << "One SHIFT..." << std::endl << std::endl;; } else if(state.first == 'r'){ // 如果是规约状态 p = AnalysisTable.getProduction(state.second); // 获得第i个产生式 p->print(); int len = p->getLen(); top -= len; // 将栈顶的符号按照产生式来规约 X = analysisStack[top]; // 获得此时的栈顶元素，据此来获得GOTO表的下一状态 analysisStack[++top] = std::make_pair(AnalysisTable.get(X.first, p->getVN()).second, p->getVN()); std::cerr << "One REDUCE..." << std::endl << std::endl;; } else if(state.first == 'a'){ // 如果是acc状态 std::cerr << "ACC!!!" << std::endl << std::endl; flag = false; } else{ // 到达分析表的其他状态，错误 grammer = false; flag = false; } } release(); // 释放资源 return grammer; // 返回结果，true表示句子符合一定的语法 }程序入口
项目调用测试入口：
// main.cpp #include<bits/stdc++.h> #include"SLRAnalysis.cpp" using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int maxn = 1e2 + 5; const int inf = 0x3f3f3f3f; int main(int argc, char *argv[]){ // freopen("in.in", "r", stdin); // freopen("out.out", "w", stdout); if(SLRAnalysis()) cout << "Yes,it is correct." << endl; else cout << "No,it is wrong." << endl; return 0; }调试数据
给出两组测试数据：
// in.in (lparen,() (ident,a) (plus,+) (number,15) (rparen,)) (times,*)// out.out No,it is wrong.// in.in (ident,akldjsfkl) (plus,+) (lparen,() (ident,alk) (times,*) (ident,askd) (minus,-) (ident,jfdkj) (times,*) (ident,ksfj) (slash,/) (ident,jsadlk) (plus,+) (lparen,() (ident,a) (slash,/) (ident,v) (minus,-) (ident,d) (plus,+) (ident,b) (rparen,)) (rparen,)) (slash,/) (ident,jfj)// out.out Yes,it is correct.实验体会
本次实验是完成 LR分析法 的自下而上分析，相比较上一次实验的预测分析法，LR分析法主要的差别是分析表的构造上，通过活前缀DFA的构造，以及由此分析得到SLR分析表，将图的转换变为表内各状态的转换。实验中，自我认为最难的并不是程序的编写，而是构造活前缀DFA以及得到分析表的步骤，这一步中画图花费了很多的时间，同时也再一次的复习了相关的理论知识内容，当这一切准备工作完成后，只需根据此编写相关的代码即可，以为上个实验已经完成了最基础的诸如符号、产生式等类的编写，所以这次只需考虑分析表以及分析程序的编写，这次实验的简化也一定程度上达到了上一次实验中 代码重复使用 的目的。实验整体难度不大，是进一步的对理论知识的复习过程。
-
语法分析器和自上而下语法分析器
2009-12-07 21:31:19词法分析器和自上而下语法分析器，其中语法分析器采用的是简单优先的方法。里面有实验原理，实验代码（界面采用MFC做的） -
编译原理课设_(词法分析、自下而上语法分析程序、生成中间代码)
2013-06-18 10:47:54编译原理课设_(词法分析、自下而上语法分析程序、生成中间代码) -
编译原理（三）语法分析：8.自下而上语法分析
2020-01-03 09:53:19文章目录一、自下而上分析1.短语2.最左归约3.移进-归约分析器（1）工作模式二、构造SLR(1)分析器1....自上而下分析的方法是产生语言的自然过程。但是对于分析源程序来讲，自下而上分析的方法更自然...展开全文文章目录
一、自下而上分析
自上而下分析的方法是产生语言的自然过程。但是对于分析源程序来讲，自下而上分析的方法更自然，因为语法分析处理的对象一开始都是终结符组成的串，而不是文法的开始符号。
同时，自下而上分析中最一般的方法，LR方法的能力比自上而下分析的LL方法要强，从而使得LR分析成为最为实用的语法分析方法。1.短语
方法：画出分析树，根据分析树分析- 短语：以非终结符为根子树中所有从左到右的叶子；
- 直接短语：只有父子关系的树中所有从左到右排列的叶子（树高为2）；
- 句柄：直接短语中最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）。
例：文法：
E→E+T|T，T→T*F|F，F→id
句型：id1+id2*id3分析树：
短语： id1+id2*id3 (E1) id2*id3 (T1) id1 (E2, T2, F1) id2 (T3, F3) id3 (F2) 直接短语： id1 (F1) id2 (F3) id3 (F2) 句柄：id1 (F1)PS：
问题：id1+id2是句型id1+id2*id3的短语吗？
答案：不是。
为什么？
① 没有一个E的子树，它的全部叶子是id1+id2；或者②找不到某个E，使得E=*>E*id3，E=＋>id1+id22.最左归约
最左归约的逆过程是一个最右推导，分别称最右推导和最左归约为规范推导和规范归约。
替换为相应产生式左部非终结符，归约符号是
<=
3.移进-归约分析器
（1）工作模式
- 工作方法：放幻灯，每个幻灯片是一个格局。
- 格局：（
#栈中内容，当前剩余输入#，改变格局的动作） - 改变格局的动作：
- 移进(shift)：输入序列中的终结符进栈。(匹配终结符)
- 归约(reduce)：将栈顶句柄替换为对应非终结符(最左归约)
- 接受(accept)：宣告分析成功
- 报错(error)：发现语法错误，调用错误恢复例程
PS：栈中保留的总是一个右句型的前缀(加上若干终结符形成句型)，称为活前缀
例3.27 用移进-归约方法分析
abbcde：abbcde<=aAbcde<=aAde<=aABe<=S
二、构造SLR(1)分析器
1.定义3.17 项目
一个LR(0)项目(简称项目)是这样一个产生式，在它右部的某个位置有一个点“.”。对于A→ε，它仅有一个项目A→.。
E→E-T|T T→T*F|F F→-F|id 的全部LR(0)项目：
E→.E-T E→E.-T E→E-.T E→E-T. E→.T E→T. T→.T*F T→T.*F T→T*.F T→T*F. T→.F T→F. F→.-F F→-.F F→-F. F→.id F→id.项目
A→α.β显示了分析过程中看到(移进)了产生式的多少。- β不为空的项目称为可移进项目，
- β为空的项目称为可归约项目。
2.拓广文法与识别活前缀的DFA
（1）拓广文法G’
G' = G∪{S'→S}
其中：S'→.S是识别S的初态，S'→S.是识别S的终态。- 目的是使最终构造的DFA状态集中具有唯一的初态和终态。
例：文法G：
E→E-T|T，T→T*F|F，F→-F|id拓广文法：
G' = G∪{E'→E}
唯一初态与终态：E'→.E和E'→E.（2）NFA（项目）→DFA（项目集）
词法分析器－“子集法” ：
- ① ε_闭包(I)：从状态集I不经任何字符能到达的状态全体；
- ② smove（I，a）：所有从I经字符a能直接到达的状态全体。
类似的两个过程：
- ①
closure(I)：从项目集I不经任何文法符号到达的项目全体； - ②
goto(I，x)：所有从I经文法符号x能直接到达的项目全体。
定义3.20
项目[S'→.S]和所有“.”不在产生式右部最左边的项目称为核心项目(kernel items)，其它“.”在产生式右部最左边的项目(不包括[S’→.S])称为非核心项目(nonkernel items)。（3）构造DFA：
- 计算DFA的初态，
I0=closure({S'→.S}) - 计算所有状态的所有状态转移，即考察每个未标记状态
Ii=closure(goto(Ii,x)))
例：G :
S→AB，A→aAb |ab，B→c |Bc拓广文法
G' = G∪{S'→S}，构造的 DFA 如下，其中 I0 为初态，I1 为终态。
（4）项目集中的冲突
冲突：
- 移进/归约冲突：
A→β1.β2和B→β1.【β1.有东西和没东西】：既可移进又可归约 - 归约/归约冲突：
A→α.和B→α.【α.都没东西】：均可指导下一步分析
解决方法：简单向前看一个终结符：
移进/归约冲突：若FIRST(β2)∩FOLLOW(B)=Φ，冲突可解决
归约/归约冲突：若FOLLOW(A)∩FOLLOW(B)=Φ，冲突可解决
【移进是看输入文法序列中的下一个字符，即项目.右部的字符，所以是FIRST(β2)；归约是舍弃当前栈中的非终结符，即项目左部。】
【交集为空，表示下一步展开是唯一的，所以冲突可解决】
-
根据陈火旺编译原理写的一个词法分析器，一个自下而上，一个自上而下的语法分析器
2018-11-06 19:41:27根据陈火旺编译原理用JAVA写的一个词法分析器，一个自下而上、一个自上而下的语法分析器 -
编译课程设计报告通过编程实现语法分析（自上而下，自下而上）的可视化过程，加深对两法分析原理思想的理解...
2010-06-02 18:43:03编译课程设计报告通过编程实现语法分析（自上而下，自下而上）的可视化过程，加深对两法分析原理思想的理解。 -
PL/0语言 自下而上语法分析 SLR分析
2020-04-23 23:38:40PL0 语言功能简单、结构清晰、可读性强，而又具备了一般高级程序设计语言的必须部分，因而 PL0 语言的编译程序能充分体现一个高级语言编译程序实现的基本方法和技术。 分析对象〈算术表达式〉的 BNF 定义如下： <... -
编译原理：自下而上语法分析
2019-05-06 00:54:47https://wenku.baidu.com/view/d0191919f61fb7360a4c65cf.html 这个比我们老师的课件清楚很多！ -
编译原理第五章自下而上语法分析总结
2018-05-21 10:49:24自上而下分析采用了移进-规约的方法进行语法分析，用一个寄存符号的栈，从输入串中将符号一个个移进栈中，使栈顶形成某一候选式的产生式，再将这部分产生式规约成该产生式左部的符号。 自上而下分析中有两种分析方法... -
【编译原理】第5章 自下而上的语法分析——优先分析法
2020-04-30 01:36:13自下而上语法分析比自上而下语法分析更有效率，对语法的限制更少。 自下而上语法分析的策略：移进–规约分析； 移进就是将一个终结符推进栈 归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结... -
【编译原理】c++实现自下而上语法分析器
2018-05-29 20:50:00写在前面：本博客为本人原创，严禁任何形式的转载！本博客只允许放在博客园（.cnblogs.com），如果您在其他网站看到... ... 基于C++语言实现的PL/0语言的算术表达式的自下而上的语法分析程序。该语言的其他语法... -
编译原理实验(三)：自下而上语法分析-根据 PL/0 语言的文法规范，编写 PL/0 语言的语法分析程序
2021-07-13 17:16:42通过设计、编制、调试一个典型的自上而下语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 选择最有代表性的语法分析方法，如递归下降分析法、预测... -
语法分析——自下而上
2021-04-13 23:22:05自下而上语法分析1.基本概念 1.基本概念 1）从分析树的底部（叶节点）向顶部（根节点）方向构造分析树 2）可以看成是将输入串w归约为文法开始符号S的过程 3）自上而下的语法分析采用最左推导方式，自底向上的语法... -
语法分析:自下而上分析
2016-11-30 18:35:29自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说，从语法树的末端开始，步步向上“归约”，直到根结。 -
语法分析：自上而下分析
2016-10-18 17:48:43语法分析器的功能，自上而下分析面临的问题，LL（1）分析法语法分析器的功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语言的语法... -
语法分析——自上而下
2020-09-30 00:44:40其实学到了这里应该清楚语法分析和词法分析的关系了。在实际编译的过程中并不是先进行一遍词法分析，再来一遍语法分析。两者其实是并行的。从缓冲区中读入一定字符串，经过词法分析合格后进行语法的审核。符合语法... -
语法分析——自下而上分析
2018-11-15 09:34:04短语：在一个句型对应的语法树中, 以某非终结符为根的一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。 直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。 句柄：... -
语法分析：自上而下分析（递归下降分析法+预测分析法）
2020-05-21 12:24:38语法分析：自上而下分析 目录语法分析：自上而下分析知识背景计算海明校验码步骤一：计算校验码位数步骤二：确定校验组步骤三：计算校验码的值得出海明校验码利用海明校验码校验数据其他总结 知识背景 百度百科： ... -
第五章自下而上的语法分析
2018-05-16 23:24:571. 重点内容 上一章讲到了语法分析中自上而下的分析方法，其主要思想是从文法的起始符出发进行句子的推导，这一章主要讲的是与其主要思想相反的自下而上的分析方法，其主要思想是从句子本身出发，进行归约，看能否... -
编译原理——自上而下的语法分析方法（LL分析法）
2021-01-27 23:46:09方式：自上而下的语法分析（推导）和自下而上的语法分析（规约） 下推自动机： 下推自动机模型： pda和fa的模型相比，多了一个下推栈 决定pda的动作因素：当前状态，读头指向的符号，下推栈栈顶符号 当输入串读... -
第五章 语法分析-自下而上分析
2018-05-17 13:06:34在上一章里面学习了自上而下的分析方法识别句子的正确性，这一章学习的是自下而上的分析方法，综合来讲这两章讲的就是语法分析。 -
编译原理语法分析-自上而下分析
2018-04-25 12:47:05语法分析的过程包括自上而下的推导和自下而上的规约。递归下降分析器的设计（LL分析，自上而下的推导）语法分析器的自动生成（LR分析，自下而上的规约）自上而下面临的问题：文法的左递归问题回溯的不确定性，要求... -
c#语法分析器（自上而下）
2009-09-17 19:45:46实现的功能： （1）选定一文法，选定...（2）允许用户输入语句并对该语句进行相应的语法分析 （3）要求显示语法树的建立过程以及跟踪分析表和分析栈的状态 （4）要提供单步运行，让用户跟踪分析器工作的每一个步骤 。 -
编译原理——自下而上的语法分析方法（算符优先分析法）
2021-01-29 09:16:03归约：自上而下的语法分析过程 过程： 初态：栈中只有#，读头指向最左边的单词符号 语法分析程序执行动作 移进读入一个单词并压入栈中，读头后移 归约，检查栈顶若干符号，能否进行归约，若能，以产生式左部... -
第五章 语法分析——自下而上分析
2018-05-18 00:13:54本章的语法分析方法与上一章的方法是相反的。上一章节是自上而下的分析，而这一章是自下而上的分析，即从输入串开始，逐步进行归约，将长的输入串归约到文法的开始符号。自上而下分析的关键问题是需要精确定义“可... -
自上而下的语法分析 - 编译原理 - 龙书
2019-05-05 14:16:10自上而下的语法分析（消除左递归，提取左因子） 自上而下的语法分析：（推导） 由根节点到叶节点 ※最左推导和最右推导 （每一步替换最左边的非终结符/每一步替换最右边的非终结符），最右...
