实验三自下而上语法分析及语义分析

（一）语法分析概述语法分析是对高级语言的句子结构进行分析，在编译过程中处于核心地位，它的主要任务是在词法分析识别出正确单词符号串的基础上，根据语言定义的语法规则，从单词符号串中识别出各种语法成分，并进行语法检查和错误处理，生成相应的语法树。

生成语法树的方法有两种，一种是自上而下另一种是自下而上。

[1]自上而下的语法分析方法是对由单词种别构成的源程序，尝试用所有可能的途径，从语法树的根结点出发，从上至下为输入符号串建立一棵语法树。

也可以说成是为输入符号串构造一个最左推导。

整个分析过程就是一种试探的过程，通过不断使用不同产生式谋求匹配输入符号串的过程。

自上而下的语法分析方法分为确定的和不确定的两种。

只有LL（1）文法才能进行确定的自上而下语法分析，在这种分析方法中面临两个问题，回溯和死循环。

通过对文法的产生式进行改造来解决这两个问题，在回溯中改造的方法是提取公共左因子，比如:A→αβ1|αβ2，改造后为A→αA’，A’→β1|β2。

死循环的改造方法是消除左递归，比如:A→Aα|β改造后为A→βA’，A’→αA’|ε。

而不确定的有递归下降分析和预测分析，前者适合手工实现，后者适合自动生成。

递归下降分析是用子程序来实现的，为每个非终结符创造一个子程序，每个子程序里面都有一个函数体，这个函数体是根据非终结符的产生式而定义展开的，当分析过程中遇到终结符时就直接匹配，如果遇到非终结符就调用相应的非终结符对应的子程序。

预测分析方法需要借助一个状态栈和一个二维分析表来实现，两者必须联合控制才能更好的实现预测分析方法。

自下而上的语法分析方法和自上而下的语法分析方法是完全不同的两种方法，但是它们产生的结果是相同的，都是构造一棵语法树，只是构造的过程不同罢了。

语法树创建的过程是把分析符号串的各个符号作为叶子结点，按照文法定义的规则，把产生式左部的非终结符作为父结点，自下而上构造此树的过程。

它的基本思想是“移进—归约”。

◆词法分析 用户必须提供一个词法分析器来读取输入流并把记号(带有值， 如果需要的话)传达到解析器。词法分析器使叫做 yylex 的整数值的 函数。这个函数返回一个整数的记号编号，它表示读取的记号的种类。 如果这个记号关联着一个值，应当把它赋予外部变量 yylval。 为使通信得以发生，解析器和词法分析器必须在记号编号上达成 一致。编号可以由 Yacc 或用户来选择。在这两种情况下，使用 C 语 言的“# define”机制允许词法分析器使用符号来返回这些编号。例如， 假定在 Yacc 规定文件的声明段中已经定义记号名字 DIGIT。 它的意图是返回一个 DIGIT 记号编号，和等于这个数字的数值 的一个值。倘若词法分析器代码位于规定文件的程序段，标识符 DIGIT 将被定义为与记号 DIGIT 关联的记号编号。 这种机制导致清晰的、易于修改的词法分析器；唯一的缺点是在 文法中需要避免使用任何在 C 语言或解析器中保留的或有意义的记 号名字；例如，使用记号名字 if 或 while 就一定会导致编译词法分 析器时出现严峻的困难。记号名字 error 保留给错误处理，不应该随 便使用。 同上所述，记号编号可以由 Yacc 或用户来选择。在缺省的条件 下，编号由 Yacc 选择。文字字符的缺省记号编号是它在本地字符集 中的字符数值。其他名字赋予从 257 开始的记号编号。 要把一个记号编号赋予一个记号(包括文字)，可以在声明段中记 号或文字的第一次出现时直接跟随着一个非负整数。这个整数被接受
第四：YACC 内部名称： ................................................................................................ 7 第五：运行结果（源代码见附录）.............................................................................. 8 第六：实验总结 ............................................................................................................... 8 第七：附录 ..................................................................................................................... 10

5
2 向前看集 Follow
定义 设文法G[S],非终结符号U的向前看集为 Follow(U)={a︱S * …Ua…， a∈ Vt∪{＃}}
即Follow(U)为所有含有U的句型中紧跟在U之 后的终结符号或＃组成的集合。 （若紧跟在非终结符号U后面的符号串为空时 ，则视U后面的符号为特殊符号＃）
从语法树建立的角度来看，它是根据文法从树根结
点开始，试着自上而下建立一棵语法树，其末端结点
按从左到右的顺序若是给定的句子，则句子得到识别，
表明其结构符合文法，否则不符合文法。
14
文法G[N]：N→D︱ND D→0︱1︱2︱…︱9
分析25是否符合该文法 N
ND D5 2
15
2 自顶向下分析的难点及解决办法
16
对于某个非终结符号有n个规则(n个候选式)， 此时要分两种情况 I 首符号不相同
10
例： 文法G[E] E→TE’
E’→+E︱є T→FT’ T’→T︱є F→PF’ F’→*F’︱є P→(E)︱a︱b︱∧
First(E)= First(T)= First(F)= First(P)=｛(,a,b,∧｝
First(E’)=｛+,є ｝ First(F’)=｛*,є ｝
First(T’)=｛(,a,b,∧,є ｝
6
例： 文法G[E]：E→E+T︱T
T→T*F︱F F→(E)︱i
E * E
E * E+T Follow（E）=｛＃，+，）｝
E * （E）
E * T
E * T+T E * T*F E * （T）
Follow（T）=｛＃，*，+，）｝Follow（F）=来自＃，*，+，）｝7

17
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。
x*y
S
IP x A y **
18
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。
x*y
S
IP x A y **
19
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
(4.3)
虽没有直接左递归，但S、Q、R都是左递归的
SQcRbcSabc
一个文法消除左递归的条件
丌含以为右部的产生式
丌含回路
PP
30
例 文法G(S): S→Qc|c Q→Rb|b R→Sa|a
(4.3)
虽没有直接左递归，但S、Q、R都是左递归的
SQcRbcSabc
Q
Q
ⅹ
S
R
S→Qc|c Q→Rb|b R→Sa|a
35
例 考虑文法G(S)
S→Qc|c Q→Rb|b R→Sa|a
消除S的直接左递归后： S→abcS | bcS | cS S→abcS | Q→Sab |ab | b R→Sa|a
关于Q和R的觃则已是多余的，化简为：
S→abcS | bcS | cS
S→abcS |
(4.4)
36
注意，由于对非终结符排序的丌同，最 后所得的文法在形式上可能丌一样。但 丌难证明，它们都是等价的。
分析输入串x*y(记为)。
x*y
S
IP
15
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。

学生实验报告（理工类）课程名称：编译原理专业班级：08计算机科学与技术(单)本所属院部：信息技术学院指导教师：洪蕾20 10 ——20 11 学年第二学期金陵科技学院教务处制实验报告书写要求实验报告原则上要求学生手写，要求书写工整。

若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。

纸张一律采用A4的纸张。

实验报告书写说明实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。

各院部可根据学科特点和实验具体要求增加项目。

填写注意事项（1）细致观察，及时、准确、如实记录。

（2）准确说明，层次清晰。

（3）尽量采用专用术语来说明事物。

（4）外文、符号、公式要准确，应使用统一规定的名词和符号。

（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。

实验报告批改说明实验报告的批改要及时、认真、仔细，一律用红色笔批改。

实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。

实验报告装订要求实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。

实验项目名称： LR(1)分析表语法分析实验学时： 6 同组学生姓名：无实验地点： B513 实验日期： 2011.4.7/4.21 实验成绩：批改教师：批改时间：一、实验目的和要求语法分析主要目的是按照程序语言的语法规则,从由词法分析输出的源程序符号串中识别出各类语法成分,同时进行语法检查,为语义分析和代码生成作准备.语法分析程序在分析过程中检查符号串是否为该程序的句子.若是则输出该句子的分析树,否则就表示源程序存在语法错误,并报告错误的性质与位置.二、实验仪器和设备主机一台：有Visual Studio 2005工具三、实验过程说明：此程序共有两个类，Lexical进行词法分析，Syntax进行语法分析.对于语法分析，采用LR(1)分析法，判断程序是否满足规定的结构.1：LR-table.txt：存放分析表，其中正数表示移进，负数表示归约，100表示接受状态，0表示不操作。

14
无关文法及分析
1. 上下文无关文法(即2型文法)的形式定义：
上下文无关文法是一个四元组(VT , VN , P , S)：
① ②
终非结终符 结集 符合 集合VTVN(与VT产的不生左相式部交)
产生式 的右部
③ 产生式或文法规则A→α形成的集合P,
其中A∈VN,α∈(VT∪VN)* 4) 开始符号S，其中S∈VN
25
无关文法及分析
3.2 上下文无关文法的形式定义
1. 上下文无关文法(即2型文法)的形式定义 2. chomsky文法的分类 3. 推导和规约的定义 4. 句型和句子的定义 5. 最左和最右推导 6. 文法定义的语言 7. 递归产生式和递归文法 8. 文法和语言
mcy
编译原理课程设计之第三章上下文
mcy
编译原理课程设计之第三章上下文
1
无关文法及分析
第三章 上下文无关文法及分析
本章的目的是为语言的语法 描述寻求形式工具，要求该 工具对程序设计语言给出精 确无二义的语法描述。
mcy
编译原理课程设计之第三章上下文
2
无关文法及分析
第三章 上下文无关文法及分析
✓3.1 语法分析过程 ▪ 3.2 上下文无关文法的形式定义
下面的2型文法描述了包含加法、减法和乘法的简 单整型算术表达式的语法结构。
文法G[exp]：
exp → exp op exp exp →(exp) exp → number
34-3 是符合该 语法结构的简单 整型算术表达式 (句子)吗？
op → + | - | *
mcy
编译原理课程设计之第三章上下文
令G是一个如上所定义的文法，则G=(VT,VN,P,S)

M[A][a]。 ④ 若 ε∈first(α) ， 则 对 于 每 个 终 结 符
b∈follow(A)，把A→α加至M[A][b]。 ⑤把所有未定义的M[A][c]标上“出错标志”
（c∈VT）。
4.7 预测分析法
㈢预测分析控制程序实现 ①数据结构 M：二维数组，存放预测分析表。 stack：符号栈，初始时为“#S”（S为开
中ε∈afi∈rsVt(XT ，)。则 a∈first(X) ； 若 X→ε ， 则 ③观察每个产生式，若有X→Y……，其
中为fYir∈st(VYN)，/ε）则加将到fifrisrts(tY(X)中)中的。非ε元素（记
4.5 first集和follow集
考虑更一般情况， Y2、…Yi-1∈VN。
始符号）。 X：表示栈顶符号 t.code：当前处理单词种别
4.7 预测分析法
②算法描述 预测分析控制程序任何时刻的动作，都
按照栈顶符号X和当前输入符号t.code行 事，控制程序每次执行下述三种可能的 动作之一（暂不考虑出错情况）。 l 若X 和 t.code 均为 '#'，则分析成功， 输入串为合法句子，终止分析过程。
4.1 带回溯的自上而下分析法概 述
从文法的开始符号出发进行推导，最终 推出确定的输入串（由单词种别构成的 源程序）。
4.1 带回溯的自上而下分析法概 述
从根结点出发，试图用一切可能的办法， 自上而下地为输入串建立一棵语法树。 或者说，为输入串寻找一个最左推导。
4.1 带回溯的自上而下分析法概 述
A→α1|α2|…|αn|ε 设当前输入符号为a，根据下述原则
if (a∈first(αi))
用A→αi推导（1≤i≤n）
else if (a∈follow(A))

第五章⾃上⽽下语法分析第五章⾃上⽽下语法分析1、教学⽬的及要求：本章介绍编译程序的第⼆个阶段语法分析的设计⽅法和实现原理，包括⾃上⽽下分析的⽆回朔的递归下降分析、 LL(1)分析法。

要求理解递归下降分析、LL(1)⽂法的基本概念；掌握⽆回朔的递归下降分析的设计和实现、LL(1)分析表的构造与分析⽅法。

◇能够对⼀个给定的⽂法判断是否是LL(1)⽂法；◇能构造预测分析表；◇能⽤预测分析⽅法判断给定的输⼊符号串是否是该⽂法的句⼦；◇能对某些⾮LL(1)⽂法做等价变换：①消除左递归②提取左公共因⼦可能会变成LL(1)⽂法。

这样可扩⼤⾃顶向下分析⽅法的应⽤。

2、教学内容：语法分析器的功能，⾃上⽽下语法分析（递归下降分析法，预测分析程序），LL（1）分析法，递归下降分析程序构造，预测分析程序。

3、教学重点：递归下降⼦程序，预测分析表构造，LL(1)⽂法。

4、教学难点：对⼀个⽂法如何判断是否是LL(1)⽂法，由于在判断 LL(1)⽂法时⽤到⽂法符号串的开始符号集合（FIRST集）和⾮终结符后跟符号集合（FOLLOW集）的计算，⽽⼀般学⽣往往因概念不清或不够细⼼对这两个集合的计算常常出错，导致判断和分析结果的错误。

5、课前思考为了了解⾃顶向下（⾃上⽽下）分析的⼀般过程和问题，请学⽣⾸先回顾本章之前介绍的有关基本概念：◇句⼦、句型和语⾔的定义是什么？◇什么叫最左推导？◇什么叫最右推导和规范推导？◇什么叫确定的⾃顶向下语法分析？◇⾃顶向下语法分析是从⽂法的开始符号出发，反复使⽤各种产⽣式，寻找与输⼊符号匹配的推导。

◇确定的⾃顶向下语法分析中⽤的是哪种推导？◇在确定的⾃顶向下语法分析过程中，当以同⼀个⾮终结符为左部的产⽣式有多个不同右部时，如何选择⽤哪个产⽣式的右部替换当前的⾮终结符？◇确定的⾃顶向下语法分析对⽂法有何限制？6、章节内容第⼀节概述第⼆节 LL(1)分析⽅法第三节递归下降分析法5.1 概述LL分析法确定的⾃上⽽下分析⾃上⽽下分析递归下降分析法语法分析不确定的⾃上⽽下分析——即带回溯的分析⽅法算符优先分析⾃下⽽上分析LR分析⼀、带回溯的⾃顶向下分析⽅法是⾃顶向下分析的⼀般⽅法，即对任⼀输⼊符号串，试图⽤⼀切可能的办法，从树根结点（识别符号）出发，根据⽂法⾃上⽽下地为输⼊串建⽴⼀棵语法树，或者说，从识别符号开始，根据⽂法为输⼊串建⽴⼀个推导序列，这种分析过程本质上是⼀种试探过程，是反复使⽤不同规则谋求匹配输⼊串的过程。

电力学院编译原理课程实验报告实验名称：实验三自下而上语法分析及语义分析院系：计算机科学与技术学院专业年级：学生：学号：指导老师：实验日期：实验三自上而下的语法分析一、实验目的：通过本实验掌握LR分析器的构造过程，并根据语法制导翻译，掌握属性文法的自下而上计算的过程。

二、实验学时：4学时。

三、实验容根据给出的简单表达式的语法构成规则（见五），编制LR分析程序，要求能对用给定的语法规则书写的源程序进行语法分析和语义分析。

对于正确的表达式，给出表达式的值。

对于错误的表达式，给出出错位置。

四、实验方法采用LR分析法。

首先给出S-属性文法的定义（为简便起见，每个文法符号只设置一个综合属性，即该文法符号所代表的表达式的值。

属性文法的定义可参照书137页表6.1），并将其改造成用LR分析实现时的语义分析动作（可参照书145页表6.5）。

接下来给出LR分析表。

然后程序的具体实现：● LR分析表可用二维数组（或其他）实现。

●添加一个val栈作为语义分析实现的工具。

编写总控程序，实现语法分析和语义分析的过程。

注：对于整数的识别可以借助实验1。

五、文法定义简单的表达式文法如下：(1)E->E+T(2)E->E-T(3)E->T(4)T->T*F(5)T->T/F(6)T->F(7)F->(E)(8)F->i五、处理程序例和处理结果例示例1：20133191*(20133191+3191)+ 3191#六、源代码【cifa.h】//cifa.h#include<string>using namespace std;//单词结构定义struct WordType{int code;string pro;};//函数声明WordType get_w();void getch();void getBC();bool isLetter();bool isDigit();void retract();int Reserve(string str);string concat(string str);【Table.action.h】//table_action.hclass Table_action{int row_num,line_num;int lineName[8];string tableData[16][8];public:Table_action(){row_num=16;line_num=8;lineName[0]=30;lineName[1]=7;lineName[2]=13;lineName[3]=8;lineName[4]=14;lineName[5]=1;lineName[6]=2;lineName[7]=15;lineName[8]=0;for(int m=0;m<row_num;m++)for(int n=0;n<line_num;n++)tableData[m][n]="";tableData[0][0]="S5";tableData[0][5]="S4";tableData[1][1]="S6";tableData[1][2]="S12";tableData[1][7]="acc";tableData[2][1]="R3";tableData[2][2]="R3";tableData[2][3]="S7";tableData[2][4]="S13";tableData[2][6]="R3";tableData[2][7]="R3";tableData[3][1]="R6";tableData[3][3]="R6"; tableData[3][4]="R6"; tableData[3][6]="R6"; tableData[3][7]="R6"; tableData[4][0]="S5"; tableData[4][5]="S4"; tableData[5][1]="R8"; tableData[5][2]="R8"; tableData[5][3]="R8"; tableData[5][4]="R8"; tableData[5][6]="R8"; tableData[5][7]="R8"; tableData[6][0]="S5"; tableData[6][5]="S4"; tableData[7][0]="S5"; tableData[7][5]="S4"; tableData[8][1]="S6"; tableData[8][2]="S12"; tableData[8][6]="S11"; tableData[9][1]="R1"; tableData[9][2]="R1"; tableData[9][3]="S7"; tableData[9][4]="S13"; tableData[9][6]="R1"; tableData[9][7]="R1"; tableData[10][1]="R4"; tableData[10][2]="R4"; tableData[10][3]="R4"; tableData[10][4]="R4"; tableData[10][6]="R4"; tableData[10][7]="R4"; tableData[11][1]="R7"; tableData[11][2]="R7"; tableData[11][3]="R7"; tableData[11][4]="R7"; tableData[11][6]="R7"; tableData[11][7]="R7"; tableData[12][0]="S5"; tableData[12][5]="S4"; tableData[13][0]="S5"; tableData[13][5]="S4"; tableData[14][1]="R2"; tableData[14][2]="R2";tableData[14][4]="S13";tableData[14][6]="R2";tableData[14][7]="R2";tableData[15][1]="R5";tableData[15][2]="R5";tableData[15][3]="R5";tableData[15][4]="R5";tableData[15][5]="R5";tableData[15][6]="R5";tableData[15][7]="R5";}string getCell(int rowN,int lineN){int row=rowN;int line=getLineNumber(lineN);if(row>=0&&row<row_num&&line>=0&&line<=line_num) return tableData[row][line];elsereturn"";}int getLineNumber(int lineN){for(int i=0;i<line_num;i++)if(lineName[i]==lineN)return i;return -1;}};【Table_go.h】//table_go.hclass Table_go{int row_num,line_num;//行数、列数string lineName[3];int tableData[16][3];public:Table_go(){row_num=16;line_num=3;lineName[0]="E";lineName[1]="T";lineName[2]="F";for(int m=0;m<row_num;m++)for(int n=0;n<line_num;n++)tableData[m][n]=0;tableData[0][0]=1;tableData[0][1]=2;tableData[0][2]=3;tableData[4][0]=8;tableData[4][1]=2;tableData[4][2]=3;tableData[6][1]=9;tableData[6][2]=3;tableData[7][2]=10;tableData[12][1]=14;tableData[12][2]=3;tableData[13][2]=15;}int getCell(int rowN,string lineNa){int row=rowN;int line=getLineNumber(lineNa);if(row>=0&&row<row_num&&line<=line_num) return tableData[row][line];elsereturn -1;}int getLineNumber(string lineNa){for(int i=0;i<line_num;i++)if(lineName[i]==lineNa)return i;return -1;}};【Stack_num.h】class Stack_num{int i; //栈顶标记int *data; //栈结构public:Stack_num() //构造函数{data=new int[100];i=-1;}int push(int m) //进栈操作{i++;data[i]=m;return i;}int pop() //出栈操作{i--;return data[i+1];}int getTop() //返回栈顶{return data[i];}~Stack_num() //析构函数{delete []data;}int topNumber(){return i;}void outStack(){for(int m=0;m<=i;m++)cout<<data[m];}};【Stack_str.h】class Stack_str{int i; //栈顶标记string *data; //栈结构public:Stack_str() //构造函数{data=new string[50];i=-1;}int push(string m) //进栈操作{i++;data[i]=m;return i;}int pop() //出栈操作{data[i]="";i--;return i;}string getTop() //返回栈顶{return data[i];}~Stack_str() //析构函数{delete []data;}int topNumber(){return i;}void outStack(){for(int m=0;m<=i;m++)cout<<data[m];}};【cifa.cpp】//cifa.cpp#include<iostream>#include<string>#include"cifa.h"using namespace std;//关键字表和对应的编码string codestring[10]={"main","int","if","then","else","return","void","cout","endl"}; int codebook[10]={26,21,22,23,24,25,27,28,29};//全局变量char ch;int flag=0;/*//主函数int main(){WordType word;cout<<"请输入源程序序列:";word=get_w();while(word.pro!="#")//#为自己设置的结束标志{cout<<"("<<word.code<<"，"<<"“"<<word.pro<<"”"<<")"<<endl;word=get_w();};return 0;}*/WordType get_w(){string str="";int code;WordType wordtmp;getch();//读一个字符getBC();//去掉空白符if(isLetter()){ //以字母开头while(isLetter()||isDigit()){str=concat(str);getch();}retract();code=Reserve(str);if(code==-1){wordtmp.code=0;wordtmp.pro=str;}//不是关键字else{wordtmp.code=code;wordtmp.pro=str;}//是关键字}else if(isDigit()){ //以数字开头while(isDigit()){str=concat(str);getch();}retract();wordtmp.code=30;wordtmp.pro=str;}else if(ch=='(') {wordtmp.code=1;wordtmp.pro="(";}else if(ch==')') {wordtmp.code=2;wordtmp.pro=")";}else if(ch=='{') {wordtmp.code=3;wordtmp.pro="{";}else if(ch=='}') {wordtmp.code=4;wordtmp.pro="}";}else if(ch==';') {wordtmp.code=5;wordtmp.pro=";";}else if(ch=='=') {wordtmp.code=6;wordtmp.pro="=";}else if(ch=='+') {wordtmp.code=7;wordtmp.pro="+";}else if(ch=='*') {wordtmp.code=8;wordtmp.pro="*";}else if(ch=='>') {wordtmp.code=9;wordtmp.pro=">";}else if(ch=='<') {wordtmp.code=10;wordtmp.pro="<";}else if(ch==',') {wordtmp.code=11;wordtmp.pro=",";}else if(ch=='\'') {wordtmp.code=12;wordtmp.pro="\'";}else if(ch=='-') {wordtmp.code=13;wordtmp.pro="-";}else if(ch=='/') {wordtmp.code=14;wordtmp.pro="/";}else if(ch=='#') {wordtmp.code=15;wordtmp.pro="#";}else if(ch=='|') {wordtmp.code=16;wordtmp.pro="|";}else {wordtmp.code=100;wordtmp.pro=ch;} return wordtmp;}void getch(){if(flag==0) //没有回退的字符ch=getchar();else //有回退字符，用回退字符，并设置标志flag=0;}void getBC(){while(ch==' '||ch=='\t'||ch=='\n')ch=getchar();}bool isLetter(){if(ch>='a'&&ch<='z'||ch>='A'&&ch<='Z')return true;elsereturn false;}bool isDigit(){if(ch>='0'&&ch<='9')return true;elsereturn false;}string concat(string str){return str+ch;}void retract(){flag=1;}int Reserve(string str){int i;for(i=0;i<=8;i++){if(codestring[i]==str) //是某个关键字，返回对应的编码return codebook[i];}if(i==9) //不是关键字return -1;}【LR.cpp】#include<iostream>#include<string>#include<cstdlib>#include"cifa.h"#include"stack_num.h"#include"stack_str.h"#include"table_action.h"#include"table_go.h"using namespace std;void process(){int stepNum=1;int topStat;Stack_num statusSTK; //状态栈Stack_str symbolSTK; //符号栈Stack_num valueSTK; //值栈WordType word;Table_action actionTAB; //行为表Table_go goTAB; //转向表cout<<"请输入源程序，以#结束：";word=get_w();//总控程序初始化操作symbolSTK.push("#");statusSTK.push(0);valueSTK.push(0);cout<<"步骤\t状态栈\t符号栈\t值栈\t当前词\t动作\t转向"<<endl;//分析while(1){topStat=statusSTK.getTop(); //当前状态栈顶string act=actionTAB.getCell(topStat,word.code);//根据状态栈顶和当前单词查到的动作//输出cout<<stepNum++<<"\t";statusSTK.outStack(); cout<<"\t";symbolSTK.outStack(); cout<<"\t";valueSTK.outStack(); cout<<"\t";cout<<word.pro<<"\t";//行为为“acc”，且当前处理的单词为#，且状态栈里就两个状态//说明正常分析结束if(act=="acc"&&word.pro=="#"&&statusSTK.topNumber()==1){cout<<act<<endl;cout<<"分析成功！"<<endl;cout<<"结果为："<<valueSTK.getTop()<<endl;return;}//读到act表里标记为错误的单元格else if(act==""){cout<<endl<<"不是文法的句子！"<<endl;cout<<"错误的位置为单词"<<word.pro<<"附近。

是一种试探过程，是反复使用不同产生 式谋求匹配输入串的过程。
9
§4.2 自上而下面临的问题
例：文法 SxAy A**|*
输入串α :x*y
S x Ay
S x Ay **
S x Ay
*
10
注：
• 回溯法也称试探法，它的基本思想是：从问题的 某一种状态（初始状态）出发，搜索从这种状态 出发所能达到的所有“状态”，当一条路走到“ 尽头”的时候（不能再前进），再后退一步或若 干步，从另一种可能“状态”出发，继续搜索， 直到所有的“路径”（状态）都试探过。这种不 断“前进”、不断“回溯”寻找解的方法，就称 作“回溯法”。
三、分析条件
1.当一个文法不含左递归,并且满足每个非终结符的 所有候选首符集两两不相交的条件,是不是就一定能 进行有效的自上而下分析了呢?
28
§4.3 LL(1)分析法
例：文法
EE+T|T TT*F|F F（E）|i
Ｅ T E’
经消去直接左递归后变成 ETE’ E’+TE’|ℇ TFT’ T’*FT’|ℇ F（E） ｜i
FIRST(A)
2.A→ε
3.A→X1 X2......XK
*
(1) * a..X2....... FIRST(X1)/{ε}
(2) * ε X2.......
FIRST(X2)/{ε}
ε
(3) * εε......ε
36
FIRST集
1.First(X)集合构造，X∈VT∪VN
例：求下题的FIRST集
25
§4.3 LL(1)分析法
3.提取公共左因子 A.事实上，许多文法均存在这样的非终结符，
其所有候选的终结首符集并非两两不相交。

高效性
由于从文法的最顶端开始分析， 一旦发现不匹配，就可以立即终 止当前分支的搜索，避免不必要 的计算，提高了编译器的效率。
易于处理左递归文
法
自上而下的分析方法可以很方便 地处理含有左递归的文法，而左 递归是许多实际编程语言的重要 特征。
局限性
无法处理左边界问题
自上而下的分析方法在处理某些含有左边界的文法时可能 会遇到问题，因为这种方法会优先匹配最左边的符号，而 左边界问题需要从右往左匹配符号。
案例三
在编译器优化中，自上而下的语法分析被用 于识别和修改源代码中的冗余和低效的语法 成分。例如，在C编译器的实现中，自上而 下的语法分析可以用于优化循环结构，减少 不必要的循环次数，提高程序的执行效率。
自上而下的语法分析还可以用于代码生成和 代码生成器的实现。通过识别和解析源代码 中的语法成分，可以生成更高效、更安全的 机器代码或字节码，提高程序的执行效率和
安全性。
THANKS
感谢观看
详细描述：递归下降分析算法易于理解，每个产生式规 则对应一个函数，函数的实现相对简单明了。
详细描述：对于每个产生式规则，需要编写相应的递归 函数，可能会导致代码冗余。
移入-规约分析算法
总结词
基于栈的算法
详细描述
移入-规约分析算法是一种自上而下的语法分 析算法，它将目标语句从左到右依次读入， 并根据文法的产生式规则进行移入或规约操 作，直到找到目标语句的语法结构。
词法分析
词法分析是编译过程的第一步，也称为扫描或词法扫描。它的任务是从左 到右读取源代码，将其分解成一个个的记号或符号。
词法分析器通常使用正则表达式或有限自动机来识别和生成记号，这些记 号可以是关键字、标识符、运算符、标点符号等。

11
根据定义计算FIRST集
1.若XV,则FIRST(X)={X}. 2.若XVN,且有产生式Xa…，aV 则
把a加入到FIRST(X)中;若X是一条产 生式,则把也加到FIRST(X)中。 3.若XY…是一个产生式且YVN,则把 FIRST(Y)中的所有非元素都加到 FIRST(X)中;
12
23
G1[S]: S →xAy A →ab | a 输入串：
xay
G2[S]: S →aAS | b A →bAS | ε 输入串：
ab
左递归
G3[S]: S →Sa | b 输入串：
baa
公因子
24
4.2.1 消除左递归
1 消除直接左递归 消除直接左递归（改写为等价的右递归）
形如：A → A α|β α非， β不以A开始 改写为： A →βB（B为新增加的非终结符）
的右部由不同的VT开始。
7
G2[S]: S →Ap S → Bq 输入串：
A → cA
A →a
W=ccap
G2文法B 特→点d：B
B→b
(1)每个产生式的右部不全由VT开始。 (2)如果两个产生式有相同的左部，那么它们
的右部由不同的VT或VN开始。 (3)文法中无空产生式
8
FIRST集定义
令G是一个上下无关文法，对G的所有非终结符 的每个候选定义它的终结首符号集FIRST() 为：
*
FIRST () = {a | a..., a VT }
特别是，若
*
，则规定FIRST()。
9
G2[S]: S →Ap S → Bq
A → cA
A →a
• 如果非终结符A的所有候B 选→首b符集两两不相交， 即A的任B何→两个dB不同候选 i和 j

一、实验目的与要求1. 实验目的(1) 理解编译原理的基本概念和流程。

(2) 掌握常用的编译方法和技术。

(3) 熟练使用编译器开发工具。

2. 实验要求(1) 熟悉计算机专业基础知识。

(2) 掌握C/C++编程语言。

(3) 了解基本的编译原理。

二、实验环境1. 硬件环境(1) 计算机一台。

(2) 编译器开发工具（如GCC、Clang等）。

2. 软件环境(1) 操作系统（如Windows、Linux等）。

(2) 文本编辑器或集成开发环境（如Visual Studio、Eclipse等）。

三、实验内容1. 实验一：词法分析(1) 实现一个简单的词法分析器，识别出关键字、标识符、常量等。

(2) 分析输入的程序，输出词法分析结果。

2. 实验二：语法分析(1) 实现一个简单的语法分析器，根据给定的语法规则分析输入的程序。

(2) 分析输入的程序，输出语法分析树。

3. 实验三：语义分析(1) 实现一个简单的语义分析器，检查程序中的语义错误。

(2) 分析输入的程序，输出语义分析结果。

4. 实验四：中间代码(1) 实现一个简单的中间代码器，将转换为中间代码表示。

(2) 对输入的程序进行转换，输出中间代码。

5. 实验五：目标代码(1) 实现一个简单的目标代码器，将中间代码转换为目标代码。

(2) 对输入的中间代码进行转换，输出目标代码。

四、实验步骤与方法1. 实验一：词法分析(1) 编写词法分析器的代码。

(2) 测试并调试词法分析器。

2. 实验二：语法分析(1) 编写语法分析器的代码。

(2) 测试并调试语法分析器。

3. 实验三：语义分析(1) 编写语义分析器的代码。

(2) 测试并调试语义分析器。

4. 实验四：中间代码(1) 编写中间代码器的代码。

(2) 测试并调试中间代码器。

5. 实验五：目标代码(1) 编写目标代码器的代码。

(2) 测试并调试目标代码器。

五、实验注意事项1. 按照实验要求编写代码，注意代码规范和可读性。

上海电力学院编译原理课程实验报告实验名称：实验三自下而上语法分析及语义分析院系：计算机科学与技术学院专业年级：学生姓名：学号：指导老师：实验日期：实验三自上而下的语法分析一、实验目的：通过本实验掌握LR分析器的构造过程，并根据语法制导翻译，掌握属性文法的自下而上计算的过程。

二、实验学时：4学时。

三、实验内容根据给出的简单表达式的语法构成规则（见五），编制LR分析程序，要求能对用给定的语法规则书写的源程序进行语法分析和语义分析。

对于正确的表达式，给出表达式的值。

对于错误的表达式，给出出错位置。

四、实验方法采用LR分析法。

首先给出S-属性文法的定义（为简便起见，每个文法符号只设置一个综合属性，即该文法符号所代表的表达式的值。

属性文法的定义可参照书137页表6.1），并将其改造成用LR分析实现时的语义分析动作（可参照书145页表6.5）。

接下来给出LR分析表。

然后程序的具体实现：●LR分析表可用二维数组（或其他）实现。

●添加一个val栈作为语义分析实现的工具。

●编写总控程序，实现语法分析和语义分析的过程。

注：对于整数的识别可以借助实验1。

五、文法定义简单的表达式文法如下：(1)E->E+T(2)E->E-T(3)E->T(4)T->T*F(5)T->T/F(6)T->F(7)F->(E)(8)F->i五、处理程序例和处理结果例示例1：20133191*(20133191+3191)+ 3191#六、源代码【cifa.h】//cifa.h#include<string> using namespace std;//单词结构定义struct WordType{int code;string pro;};//函数声明WordType get_w();void getch();void getBC();bool isLetter();bool isDigit();void retract();int Reserve(string str); string concat(string str); 【Table.action.h】//table_action.hclass Table_action{int row_num,line_num;int lineName[8];string tableData[16][8]; public:Table_action(){row_num=16;line_num=8;lineName[0]=30;lineName[1]=7;lineName[2]=13;lineName[3]=8;lineName[4]=14;lineName[5]=1;lineName[6]=2;lineName[7]=15;lineName[8]=0;for(int m=0;m<row_num;m++) for(int n=0;n<line_num;n++) tableData[m][n]="";tableData[0][0]="S5";tableData[0][5]="S4";tableData[1][1]="S6";tableData[1][2]="S12";tableData[1][7]="acc";tableData[2][1]="R3";tableData[2][2]="R3";tableData[2][3]="S7";tableData[2][6]="R3"; tableData[2][7]="R3"; tableData[3][1]="R6"; tableData[3][2]="R6"; tableData[3][3]="R6"; tableData[3][4]="R6"; tableData[3][6]="R6"; tableData[3][7]="R6"; tableData[4][0]="S5"; tableData[4][5]="S4"; tableData[5][1]="R8"; tableData[5][2]="R8"; tableData[5][3]="R8"; tableData[5][4]="R8"; tableData[5][6]="R8"; tableData[5][7]="R8"; tableData[6][0]="S5"; tableData[6][5]="S4"; tableData[7][0]="S5"; tableData[7][5]="S4"; tableData[8][1]="S6";tableData[8][6]="S11"; tableData[9][1]="R1"; tableData[9][2]="R1"; tableData[9][3]="S7"; tableData[9][4]="S13"; tableData[9][6]="R1"; tableData[9][7]="R1"; tableData[10][1]="R4"; tableData[10][2]="R4"; tableData[10][3]="R4"; tableData[10][4]="R4"; tableData[10][6]="R4"; tableData[10][7]="R4"; tableData[11][1]="R7"; tableData[11][2]="R7"; tableData[11][3]="R7"; tableData[11][4]="R7"; tableData[11][6]="R7"; tableData[11][7]="R7"; tableData[12][0]="S5"; tableData[12][5]="S4";tableData[13][5]="S4";tableData[14][1]="R2";tableData[14][2]="R2";tableData[14][3]="S7";tableData[14][4]="S13";tableData[14][6]="R2";tableData[14][7]="R2";tableData[15][1]="R5";tableData[15][2]="R5";tableData[15][3]="R5";tableData[15][4]="R5";tableData[15][5]="R5";tableData[15][6]="R5";tableData[15][7]="R5";}string getCell(int rowN,int lineN){int row=rowN;int line=getLineNumber(lineN);if(row>=0&&row<row_num&&line>=0&&line<=line_num) return tableData[row][line];elsereturn"";}int getLineNumber(int lineN){for(int i=0;i<line_num;i++)if(lineName[i]==lineN)return i;return -1;}};【Table_go.h】//table_go.hclass Table_go{int row_num,line_num;//行数、列数string lineName[3];int tableData[16][3];public:Table_go(){row_num=16;line_num=3;lineName[0]="E";lineName[1]="T";lineName[2]="F";for(int m=0;m<row_num;m++) for(int n=0;n<line_num;n++)tableData[m][n]=0;tableData[0][0]=1;tableData[0][1]=2;tableData[0][2]=3;tableData[4][0]=8;tableData[4][1]=2;tableData[4][2]=3;tableData[6][1]=9;tableData[6][2]=3;tableData[7][2]=10;tableData[12][1]=14;tableData[12][2]=3;tableData[13][2]=15;}int getCell(int rowN,string lineNa){int row=rowN;int line=getLineNumber(lineNa);if(row>=0&&row<row_num&&line<=line_num) return tableData[row][line];elsereturn -1;}int getLineNumber(string lineNa){for(int i=0;i<line_num;i++)if(lineName[i]==lineNa)return i;return -1;}};【Stack_num.h】class Stack_num{int i; //栈顶标记int *data; //栈结构public:Stack_num() //构造函数{data=new int[100];i=-1;}int push(int m) //进栈操作{i++;data[i]=m;return i;}int pop() //出栈操作{i--;return data[i+1];}int getTop() //返回栈顶{return data[i];}~Stack_num() //析构函数{delete []data;}int topNumber(){return i;}void outStack(){for(int m=0;m<=i;m++)cout<<data[m];}};【Stack_str.h】class Stack_str{int i; //栈顶标记string *data; //栈结构public:Stack_str() //构造函数{data=new string[50];i=-1;}int push(string m) //进栈操作{i++;data[i]=m;return i;}int pop() //出栈操作{data[i]="";i--;return i;}string getTop() //返回栈顶{return data[i];}~Stack_str() //析构函数{delete []data;int topNumber(){return i;}void outStack(){for(int m=0;m<=i;m++)cout<<data[m];}};【cifa.cpp】//cifa.cpp#include<iostream>#include<string>#include"cifa.h"using namespace std;//关键字表和对应的编码stringcodestring[10]={"main","int","if","then","else","return","void","cout","endlint codebook[10]={26,21,22,23,24,25,27,28,29};//全局变量char ch;int flag=0;/*//主函数int main(){WordType word;cout<<"请输入源程序序列:";word=get_w();while(word.pro!="#")//#为自己设置的结束标志{cout<<"("<<word.code<<"，"<<"“"<<word.pro<<"”"<<")"<<endl;word=get_w();};return 0;}*/WordType get_w(){string str="";int code;WordType wordtmp;getch();//读一个字符getBC();//去掉空白符if(isLetter()){ //以字母开头while(isLetter()||isDigit()){str=concat(str);getch();}retract();code=Reserve(str);if(code==-1){wordtmp.code=0;wordtmp.pro=str;}//不是关键字else{wordtmp.code=code;wordtmp.pro=str;}//是关键字}else if(isDigit()){ //以数字开头while(isDigit()){str=concat(str);getch();}retract();wordtmp.code=30;wordtmp.pro=str;}else if(ch=='(') {wordtmp.code=1;wordtmp.pro="(";} else if(ch==')') {wordtmp.code=2;wordtmp.pro=")";} else if(ch=='{') {wordtmp.code=3;wordtmp.pro="{";} else if(ch=='}') {wordtmp.code=4;wordtmp.pro="}";} else if(ch==';') {wordtmp.code=5;wordtmp.pro=";";} else if(ch=='=') {wordtmp.code=6;wordtmp.pro="=";} else if(ch=='+') {wordtmp.code=7;wordtmp.pro="+";} else if(ch=='*') {wordtmp.code=8;wordtmp.pro="*";} else if(ch=='>') {wordtmp.code=9;wordtmp.pro=">";} else if(ch=='<') {wordtmp.code=10;wordtmp.pro="<";} else if(ch==',') {wordtmp.code=11;wordtmp.pro=",";} else if(ch=='\'') {wordtmp.code=12;wordtmp.pro="\'";} else if(ch=='-') {wordtmp.code=13;wordtmp.pro="-";} else if(ch=='/') {wordtmp.code=14;wordtmp.pro="/";} else if(ch=='#') {wordtmp.code=15;wordtmp.pro="#";} else if(ch=='|') {wordtmp.code=16;wordtmp.pro="|";}else {wordtmp.code=100;wordtmp.pro=ch;}return wordtmp;}void getch(){if(flag==0) //没有回退的字符ch=getchar();else //有回退字符，用回退字符，并设置标志flag=0;}void getBC(){while(ch==' '||ch=='\t'||ch=='\n')ch=getchar();}bool isLetter(){if(ch>='a'&&ch<='z'||ch>='A'&&ch<='Z')return true;elsereturn false;}bool isDigit(){if(ch>='0'&&ch<='9')return true;elsereturn false;}string concat(string str){return str+ch;}void retract(){flag=1;}int Reserve(string str){int i;for(i=0;i<=8;i++){if(codestring[i]==str) //是某个关键字，返回对应的编码return codebook[i];}if(i==9) //不是关键字return -1;}【LR.cpp】#include<iostream>#include<string>#include<cstdlib>#include"cifa.h"#include"stack_num.h"#include"stack_str.h"#include"table_action.h"#include"table_go.h"using namespace std;void process(){int stepNum=1;int topStat;Stack_num statusSTK; //状态栈Stack_str symbolSTK; //符号栈Stack_num valueSTK; //值栈WordType word;Table_action actionTAB; //行为表Table_go goTAB; //转向表cout<<"请输入源程序，以#结束：";word=get_w();//总控程序初始化操作symbolSTK.push("#");statusSTK.push(0);valueSTK.push(0);cout<<"步骤\t状态栈\t符号栈\t值栈\t当前词\t动作\t转向"<<endl;//分析while(1){topStat=statusSTK.getTop(); //当前状态栈顶string act=actionTAB.getCell(topStat,word.code);//根据状态栈顶和当前单词查到的动作//输出cout<<stepNum++<<"\t";statusSTK.outStack(); cout<<"\t";symbolSTK.outStack(); cout<<"\t";valueSTK.outStack(); cout<<"\t";cout<<word.pro<<"\t";//行为为“acc”，且当前处理的单词为#，且状态栈里就两个状态//说明正常分析结束if(act=="acc"&&word.pro=="#"&&statusSTK.topNumber()==1){cout<<act<<endl;cout<<"分析成功！"<<endl;cout<<"结果为："<<valueSTK.getTop()<<endl;return;}//读到act表里标记为错误的单元格else if(act==""){cout<<endl<<"不是文法的句子！"<<endl;cout<<"错误的位置为单词"<<word.pro<<"附近。

《编译原理》教学大纲一课程简介本课程是计算机科学与技术专业的专业核心课程。

本课程主要讲述高级语言翻译为汁算机能执行的代码的原理、过程、方法和技术，核心是介绍髙级语言到汇编语言的翻译。

让学生理解编译和高级语言程序之间的关系, 掌握词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等各个阶段的原理、方法和实现技术，真正认识计算机信息处理的实质、训练抽象思维能力、体验系统软件的开发过程，进一步提升计算机科学与技术的专业素养。

二课程目标（一）课程具体目标1.掌握形式语言和自动机的基本概念，理解高级语言编译的基本原理，并能够将这些原理应用于高级语言的设计之中；（毕业要求1.3掌握汁算机基础理论，能够用于对计算机应用系统的设计方案和模型进行推理和验证。

）2.能够理解现有某高级语言的编译系统中各模块的功能和实现方法，能够对不同方法的优劣进行对比和分析：（毕业要求4.1能够运用科学方法，对计算机领域的复杂工程问题进行需求和功能分析。

）3.理解编译程序的结构及各个模块的功能，利用软件工程方法分析和设计某语言的编译程序的各个模块，并能够选择合适的方法实现。

（毕业要求1.4能够运用专业知识，对计算机领域复杂工程问题的解决方案进行分析、改进。

）（二）课程目标与毕业要求的关系本课程目标主要支撑的毕业要求指标点如表1所示。

除表1所列举指标点外，根据学生特点、本课程教学特色，教学目标还涉及对毕业要求5 （选择和使用现代工具）等能力培养，为弱支撑，不在表1中列举。

（三）教学内容安排总体思路本课程的教学内容，以课程具体目标为总体指导进行制左。

通过形式语言与自动机的相关基础知识、高级语言到汇编语言的翻译原理、方法和实现技术等教学内容，传授基于某种髙级语言编译程序构造的一般原理和基本方法, 如词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等各个阶段的原理等知识，从而有针对性地培养学生模型构建能力（课程目标1）、系统分析能力（课程目标2）和方案选择与实现能力（课程目标3）。

编译原理实验报告实验名称：分析调试语义分析程序实验类型：验证型指导教师：专业班级：姓名：学号：实验地点：实验成绩：日期：2016 年 6 月 3 日实验三分析调试语义分析程序一、实验目的通过分析调试TEST语言的语义分析和中间代码生成程序，加深对语法制导翻译思想的理解，掌握将语法分析所识别的语法范畴变换为中间代码的语义翻译方法。

二、实验知识1.语法制导基本思想语法制导就是对文法中的每个产生式都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。

基本思想是，根据翻译的需要设置文法符号的属性，以描述语法结构的语义。

例如，一个变量的属性有类型，层次，存储地址等。

表达式的属性有类型，值等。

属性值的计算和产生式相联系。

随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。

2.翻译方案设计1）设计原理：在实验二的基础上为文法符号引进一组属性及相应求值规则和动作，得到属性翻译文法，并引进一个符号表（包括变量名，变量数据是否有效，变量地址，变量的具体数据，数据类型等），在进行语法分析的同时，结合符号表完成语义分析与检测，同时根据属性翻译文法的属性及相关动作得到中间代码（抽象机式汇编指令），最后通过模拟的抽象机运行出结果。

2）设计方法：（@为动作标志，↓为继承属性，↑为综合属性）结合课本语法制导相关内容对文法增加属性和动作如下：以下列出有修改的属性翻译文法：①<declaration_stat>↓vartablep,datap,codep →int ID↑n@name-def↓n,t;其中动作符号的含义如下@name-def↓n,t：插入符号表；②<if_stat>→if (<expr>)@BRF↑label1<statement>@BR↑label2 @SETlabel↓label1| if (<expr>) @BRF↑label1<statement >@BR↑label2 @SETlabel↓label1else < statement > @SETlabel↓label2其中动作符号的含义如下@BRF↑label1 ：输出BRF label1；@BR↑label2：输出BR label2；@SETlabel↓label1：设置标号label1；@SETlabel↓label2：设置标号label2；③<while_stat>→while@SETlabel↑label1(<expression>) @BRF↑label2<statement >@BR↓label1 @SETlabel↓label2其中动作符号的含义如下@SETlabel↑label1：设置标号label1；@BRF↑label2 ：输出BRF label2；@BR↓label1：输出BR label1；@SETlabel↓label2：设置标号label2；④<for_stat>→for (<expression>@POP;@SETlabel↑label1< expression >@BRF↑label2@BR↑label3;@SETlabel↑label4 < expression >@POP@BR↓label1) @SETlabel↓label3 < statement >@BR↓label4@SETlabel↓label2其中动作符号的含义如下@SETlabel↓label1：设置标号label1；@BRF↑label2 ：输出BRF label2；@BR↑label3：输出BR label3；@SETlabel↓label4：设置标号label4；@BR↑label1：输出BR label1；@SETlabel↓label3：设置标号label3；@BR↑label4：输出BR label4；@SETlabel↓label2：设置标号label2；⑤<write_stat>→write <expression>@OUT;其中动作符号的含义如下@ OUT：输出OUT⑥<read_stat>→read ID↑n LOOK↓n↑d @IN@STO↓d@POP;其中动作符号的含义如下@LOOK↓n↑d:查符号表n，给出变量地址d；没有，变量没定义；@IN：输出IN；@STO↓d：输出指令代码STO d；@POP：将栈顶元素出栈⑦<expression>→ID↑n@LOOK↓n↑d@ASSIGN=<bool_expr>@STO↓d@POP |<bool_expr>其中动作符号的含义如下@LOOK↓n↑d:查符号表n，给出变量地址d；没有，变量没定义；@ASSIGN：记住当前文件位置；@STO↓d：输出指令代码STO d；⑧<bool_expr>→<additive_expr>|< additive_expr >><additive_expr>@GT|< additive_expr ><<additive_expr>@LES|< additive_expr >>=<additive_expr >@GE|< additive_expr ><=< additive_expr >@LE|< additive_expr >==< additive_expr >@EQ|< additive_expr >!=< additive_expr >@NOTEQ其中动作符号的含义如下@GT：次栈顶与栈顶作大于比较；@LES：次栈顶与栈顶作小于比较；@GE：次栈顶与栈顶作大于等于比较；@LE：次栈顶与栈顶作小于等于比较；@EQ：次栈顶与栈顶作等于比较；@NOTEQ：次栈顶与栈顶作不等于比较；B→+<term>B@ADD | -<term>B@SUB | ε⑨<additive_A>→+<term><additive_A>@ADD | -<term><additive_A>@SUB | ε其中动作符号的含义如下@ADD：操作数相加；@SUB：操作数相减；C→*<factor>C@MULT | /<factor>C@DIV | ε⑩<term_A>→*<factor><term_A>@MULT | /<factor><term_A>@DIV | ε其中动作符号的含义如下@MULT：操作数相乘；@DIV：操作数相除；⑪< factor >→(< expression >)| ID↑n@LOOK↓n↑d@LOAD↓d |NUM↑i@LOADI↓i其中动作符号的含义如下@LOOK↓n↑d：查符号表n，给出变量地址d；没有，变量没定义；@LOAD↓d：将地址d的变量入栈；@LOADI↓i：将常量i入栈；3)设计结果：1) <program>→{<declaration_list><statement_list>}2)<declaration_list>→<declaration_stat> <declaration_list>| ε3) <declaration_stat>↓vartablep,datap,codep →int ID↑n@name-def↓n,t;4) <statement_list>→<statement><statement_list>| ε5) <statement>→<if_stat>|<while_stat>|<for_stat>|<read_stat>|<write_stat>|< compound_stat > |<expression_stat>6)<if_stat>→if (<expr>)@BRF↑label1<statement>@BR↑label2 @SETlabel↓label1| if (<expr>) @BRF↑label1<statement >@BR↑label2 @SETlabel↓label1else < statement > @SETlabel↓label27)<while_stat>→while@SETlabellabel1(<expression>)@BRF↑label2 <statement >@BR ↓label1 @SETlabel↓label28) <for_stat>→for (<expression>;@SETlabel↑label1< expression >@BRF↑label2@BR↑label3;@SETlabel↑label4 < expression >@BR↓label1) @SETlabel↓label3 < statement >@BR ↓label29) <write_stat>→write <expression>@OUT;10) <read_stat>→read ID↑n LOOK↓n↑d @IN@STO↓d@POP;11)<compound_stat>→{<statement_list>}12)<expression_stat>→< expression >@POP;|;13) <expression>→ID↑n@LOOK↓n↑d@ASSIGN=<bool_expr>@STO↓d@POP |<bool_expr>14) <bool_expr>→<additive_expr><bool_A>15) <bool_A>→><additive_expr>@GT|<<additive_expr>@LES|>=<additive_expr >@GE|<=< additive_expr >@LE|==< additive_expr >@EQ|!=< additive_expr >@NOTEQ | ε16) < additive_expr>→<term><additive_A>17) <additive_A>→+<term><additive_A>@ADD | -<term><additive_A>@SUB | ε18) < term >→<factor><term_A>19) <term_A>→*<factor><term_A>@MULT | /<factor><term_A>@DIV | ε20) < factor >→(< expression >)| ID↑n@LOOK↓n↑d@LOAD↓d |NUM↑i@LOADI↓i三、实验过程首先，理解书上的代码和观看相关的知识的PPT，深入理解属性反应文法的作用，据此在我之前实验写好的语法分析基础上进行修改，写出语义分析代码。

语法分析器实验报告实验报告：语法分析器的设计与实现摘要：语法分析器是编译器的一个重要组成部分，主要负责将词法分析器输出的词法单元序列进行分析和解释，并生成语法分析树。

本实验旨在设计与实现一个基于上下文无关文法的语法分析器，并通过实现一个简单的编程语言的解释器来验证其功能。

1.引言在计算机科学中，编译器是将高级程序语言转化为机器语言的一种工具。

编译器通常由词法分析器、语法分析器、语义分析器、中间代码生成器、优化器和目标代码生成器等多个模块组成。

其中，语法分析器负责将词法分析器生成的词法单元序列进行进一步的分析与解释，生成语法分析树，为后续的语义分析和中间代码生成提供基础。

2.设计与实现2.1上下文无关文法上下文无关文法（CFG）是指一类形式化的语法规则，其中所有的产生式规则都具有相同的左部非终结符，且右部由终结符和非终结符组成。

语法分析器的设计与实现需要依据给定的上下文无关文法来进行，在本实验中，我们设计了一个简单的CFG，用于描述一个名为"SimpleLang"的编程语言。

2.2预测分析法预测分析法是一种常用的自顶向下的语法分析方法，它利用一个预测分析表来决定下一步的推导选择。

预测分析表的构造依赖于给定的上下文无关文法，以及文法的FIRST集和FOLLOW集。

在本实验中，我们使用了LL(1)的预测分析法来实现语法分析器。

2.3语法分析器实现在实现语法分析器的过程中，我们首先需要根据给定的CFG构造文法的FIRST集和FOLLOW集，以及预测分析表。

接下来，我们将词法分析器输出的词法单元序列作为输入，通过不断地匹配输入符号与预测分析表中的预测符号，进行语法分析和推导。

最终，根据CFG和推导过程，构建语法分析树。

3.实验结果与分析通过实验发现，自顶向下的预测分析法在对简单的编程语言进行语法分析时具有较高的效率和准确性。

语法分析器能够正确地识别输入程序中的语法错误，并生成相应的错误提示信息。