【习题】第05章 自底向上的语法分析
《编译原理》课后练习第05章自底向上的语法分析
课后练习
第05章自底向上的语法分析
1.S→aS|bS|a
(1) 构造该文法的LR(0)项目集规范族。
(2) 构造识别该文法所产生的活前缀的DFA。
(3) 构造其SLR分析表，并判断该文法是否是SLR(1)文法。
2.构造识别下列文法的所有活前缀的DFA
S →A|B
A →aAc
A →a
B →bBd
B →b
3.给定文法G: S → (L | a L → S, L | )
(1) 构造拓广文法及拓广文法的LR(0)项目集规范族(状态集合)。
(2) 构造这个文法的SLR（1）分析表。
4.证明AdBd是文法G[S]的活前缀。说明活前缀在LR分析中的作用。给出串dbdb#的LR
分析过程。
G[S]：(1) S→AdB
(2)A→a
(3) A→ε
(4) B→b
(5)B→Bdb
(6)B→ε
共1页，第1页
语法分析程序报告
xx理工大学 《编译原理》 题目语法分析程序 姓名： 学号： 班级：
一、实验目的 编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。 二、实验要求 利用C语言编制递归下降分析程序，并对简单语言进行语法分析。 2.1 待分析的简单语言的语法 用扩充的BNF表示如下： ⑴<程序>：：=begin<语句串>end ⑵<语句串>：：=<语句>{；<语句>} ⑶<语句>：：=<赋值语句> ⑷<赋值语句>：：=ID：=<表达式> ⑸<表达式>：：=<项>{+<项> | -<项>} ⑹<项>：：=<因子>{*<因子> | /<因子> ⑺<因子>：：=ID | NUM | （<表达式>） 2.2 实验要求说明 输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。 例如： 输入begin a:=9; x:=2*3; b:=a+x end # 输出success 输入x:=a+b*c end # 输出error 2.3 语法分析程序的酸法思想 ⑴主程序示意图如图2-1所示。 图2-1 语法分析主程序示意图 ⑵递归下降分析程序示意图如图2-2所示。 ⑶语句串分析过程示意图如图2-3所示。
图2-2 递归下降分析程序示意图 图2-3 语句串分析示意图 ⑷statement 语句分析程序流程如图2-4、2-5、2-6、2-7所示。 图2-4 statement 语句分析函数示意图 图2-5 expression 表达式分析函数示意图
图2-7 factor分析过程示意图三、语法分析程序的C语言程序源代码 #include "stdio.h" #include "string.h" char prog[100],token[8],ch; char *rwtab[6]={"begin","if","then","while","do","end"}; int syn,p,m,n,sum; int kk; factor(); expression(); yucu(); term(); statement(); lrparser(); scaner(); main() { p=kk=0; printf("\nGrade:05 Class:03 Name:Qiyubing Number:200507096 \n"); printf("\n----Please input the string end with '#':-------- \n"); do
语法分析程序实验报告及代码
LL(1)语法分析实验报告 一、实验题目 LL（1）语法分析 二、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，检查语法错误，进一步掌握常用的语法分析方法。 三、实验内容 构造LL(1)语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合则输出错误信息。 消除递归前的文法消除递归和提取公因子后的等价文法 S →S ∨ a T | a T | ∨ a T S→aTS’ |vaTS’ T →∧ a T | ∧a S’→vaTS’ |ε T→∧ a T’ T’→∧ aT’ |ε 根据已建立的分析表，对下列输入串：a∧ a∧ a进行语法分析，判断其是否符合文法。 四、实验要求 1.根据已由的文法规则建立LL（1）分析表； 2.输出分析过程。 请输入待分析的字符串: a∧ a∧ a 符号栈输入串所用产生式
#S a∧ a∧ a# #S’Ta a∧ a∧ a# S→aTS’ #S’T ∧ a∧ a# # S’T’a∧∧ a∧ a# T→∧ a T’ # S’T’a a∧ a# # S’T’∧ a# # S’T’a∧∧ a# T’→∧ aT’ # S’ T’a a# # S’ T’# # S’ # T’→ε # # S’→ε 五、程序思路 模块结构： 1、定义部分：定义常量、变量、数据结构。 2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）； 3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则； 4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。 六、程序源代码 /* 程序名称： LL(1)文法分析程序 */ /* S->S>aT|aT|>aT */ /* T-> 实习二语法分析－自上而下分析 一、实验目的 使用预测分析方法对输入的表达式进行分析，掌握其具体的使用并且学会去分析一个文法。 二、实验内容 1．设计表达式的语法分析器算法（使用预测分析） 2．编写一段代码并上机调试查看其运行结果 三、实验要求 使用LL（1）分析算法设计表达式的语法分析器 LL（1）文法是一个自上而下的语法分析方法，它是从文法的开始符号出发，生成句子的最左推导，从左到右扫描源程序，每次向前查看一个字符，确定当前应该选择的产生式。 实现LL（1）分析的另一种有效方法是使用一张分析表和一个栈进行联合控制。 预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前a的输入符号行事的。对于任何（X，a），总控程序每次都执行三种可能的动作之一。 1.若X＝a＝“#”，则宣布分析成功，停止分析过程 2.若X＝a≠“#”，则把X从STACK栈顶逐出，让a指向下一 个输入符号。 3.若X是一个非终结符，则查看分析表。 四、运行结果 （本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析） 五、源程序实现 /*LL(1)分析法源程序，只能在VC++中运行*/ #include #include #include 词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。 课后练习参考答案 第05章 自底向上的语法分析 1. S→aS|bS|a (1) 构造该文法的LR(0)项目集规范族。 (2) 构造识别该文法所产生的活前缀的DFA 。 (3) 构造其SLR 分析表，并判断该文法是否是SLR(1)文法。 【解】 构造LR(0)项目集规范族，有两种方法：一种是利用有限自动机来构造，另一种是利用函数CLOSURE 和GO 来构造。本题采取第2种方法，通过计算函数CLOSURE 和GO 得到文法的LR(0)项目集规范族，而GO 函数则把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA 。 (1) 将文法G(S)拓广为G(S’)： (0)S’→S (1)S→aS (2)S→bS (3)S→a 构造该文法的LR(0)项目集规范族： I 0=CLOSURE({S →·S})={S’ →·S, S→·aS, S→·bS, S→·a} I 1=GO( I 0 , a)=CLOSURE({S→a·S , S→a·})={S→a·S , S→a· , S→·aS, S→·bS, S→·a } I 2=GO(I 0 , b)=CLOSURE({S→b·S })={ S→b·S, S→·aS, S→·bS, S→·a } I 3=GO(I 0 , S)=CLOSURE({S’ →S·})={ S’ →S·} GO(I 1, a)=CLOSURE({S→a·S , S→a·})=I 1 GO(I 2, b)=CLOSURE({S→b·S})=I 2 I 4=GO(I 1, S)=CLOSURE({S→aS·})={S→aS·} GO(I 2, a)= CLOSURE({S→a·S , S→a·})=I 1 GO(I 2, b)= CLOSURE({S→b·S})=I 2 I 5=GO(I 2, S)=CLOSURE({S→bS·})={ S→bS·} 所以，项目集I 0，I 1，I 2，I 3，I 4和I 5构成了该文法的LR(0)项目集规范族。 实验内容： 可选择LL1分析法、算符优先分析法、LR分析法之一，实现如下表达式文法的语法分析器： （1）E→E+T | E-T | T （2）T→T*F | T/F | F （3）F→P^F | P （4）P→(E) | i 实验环境： Windows XP 实验分析： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分 实验程序： #include {'r','r','s','r','r','r'}, {'r','r','r','r','r','r'}, {'r','r','r','r','r','r'} }; char snum[12][6]={//数字表 {5,1,1,4,2,1}, {3,6,5,3,2,0}, {2,2,7,2,2,2}, {4,4,4,4,4,4}, {5,1,1,4,2,1}, {6,6,6,6,6,6}, {5,1,1,4,2,1}, {5,1,1,4,2,1}, {3,6,5,3,11,4}, {1,1,7,1,1,1}, {3,3,3,3,3,3}, {5,5,5,5,5,5} }; int go2[12][3]={//goto表 {1,2,3}, {0,0,0}, {0,0,0}, {0,0,0}, {8,2,3}, {0,0,0}, {0,9,3}, {0,0,10}, {0,0,0}, {0,0,0}, {0,0,0}, {0,0,0} }; void action(int i,char *&a,char &how,int &num,char &A,int &b)//action函数[i,a] { int j; switch(*a) { case 'i': j=0;break; case '+': j=1;break; case '*': j=2;break; case '(': 第三次上机-语法分析1 目的：熟练掌握自上而下的语法分析方法，并能用程序实现。 要求： 1. 使用的文法如下： E TE E +TE|ε T FT T *FT|ε F (E)|id 2. 对于任意给定的输入串（词法记号流）进行语法分析，递归下降方法和非递归预测分析方法可以任选其一来实现。 3. 要有一定的错误处理功能即对错误能提示，并且能在一定程度上忽略尽量少的记号来进行接下来的分析。可以参考书上介绍的同步记号集合来处理。 可能的出错情况：idid*id, id**id, （id+id，+id*+id …… 4. 输入串以#结尾，输出推导过程中使用到的产生式。例如： 输入：id+id*id# 输出： E TE' T FT' F id E +TE' T FT' …… 如果输入串有错误，则在输出中要体现是跳过输入串的某些记号了，还是弹栈，弹出某个非终结符或者是终结符了，同时给出相应的出错提示信息。比如： idid*id对应的出错信息是："输入串跳过记号id，用户多输入了一个id"； id**id对应的出错信息是："弹栈，弹出非终结符F，用户少输入了一个id" (id+id对应的出错信息是："弹栈，弹出终结符) ，用户少输入了一个右括号（或者说，括号不匹配）" 有余力的同学可进一步考虑如下扩展： 1. 将递归下降方法和非递归预测分析方法都实现 2. 在语法分析的过程中调用前两次上机的结果，即利用词法分析器来返回一个记号给语法分析器。 3. 编写First和Follow函数，实现其求解过程。 */ #include public class Accept2 { public static StringBuffer stack=new StringBuffer("#E"); public static StringBuffer stack2=new StringBuffer("i+i*#"); public static void main(String arts[]){ //stack2.deleteCharAt(0); System.out.print(accept(stack,stack2)); } public static boolean accept(StringBuffer stack,StringBuffer stack2){//判断识别与否 boolean result=true; outer:while (true) { System.out.format("%-9s",stack+""); System.out.format("%9s",stack2+"\n"); char c1 = stack.charAt(stack.length() - 1); char c2 = stack2.charAt(0); if(c1=='#'&&c2=='#') return true; switch (c1) { case'E': if(!E(c2)) {result=false;break outer;} break; case'P': //P代表E’if(!P(c2)) {result=false;break outer;} break; case'T': if(!T(c2)) {result=false;break outer;} break; case'Q': //Q代表T’if(!Q(c2)) {result=false;break outer;} break; case'F': if(!F(c2)) {result=false;break outer;} break; default: {//终结符的时候 if(c2==c1){ stack.deleteCharAt(stack.length()-1); stack2.deleteCharAt(0); //System.out.println(); } else{ 第五章自上而下语法分析 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分析 一、带回溯的自顶向下分析方法 是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的办法，从树根结点（识别符号）出发，根据文法自上而下地为输入串建立一棵语法树，或者说，从识别符号开始，根据文法为输入串建立一个推导序列，这种分析过程本质上是一种试探过程，是反复使用不同规则谋求匹配输入串的过程。 例有文法G[S]：S→cAd，A→ab|a，输入串w=cad。其分析过程为带回溯的。 二、存在问题及解决办法 1、左递归问题： 自顶向下分析方法只有把规则排列得合适时才能正确工作，该方法不能处理具有左递归性文法，可采取某些算法消除左递归。 2、回溯问题： 语法分析实验报告 一、实验目的： 1. 了解单词(内部编码)符号串中的短语句型结构形成规律。 2. 理解和掌握语法分析过程中语法分析思想(LL，LR)的智能算法化方法。 二、实验内容： 构造自己设计的小语言的语法分析器： 1. 小语言的语法描述(语法规则)的设计即文法的设计； 2. 把文法形式符号中所隐含的信息内容挖掘出来并用LL或LR 的资料形式(分析表)表示出来； 3. 语法分析的数据输入形式和输出形式的确定； 4. 语法分析程序各个模块的设计与调试。 主要设备和材料：电脑、winxp操作系统、VC语言系统 三、实验分工： 四、实验步骤： 1、语法规则 ①<程序>::= {<变量定义语句>|<赋值语句>|<条件语句> |<循环语句> } ②<变量定义语句>::=var 变量{，变量}； ③<赋值语句>::=变量：= <表达式>； ④<表达式>::=标识符{运算符标识符}； ⑤<标识符>::=变量|常量 ⑥<运算符>::=+ | - | * | / | >= | <= ⑦<条件语句>::= 环语句} [end] ⑩<循环语句>::=while(表达式) [begin] {赋值语句| 条件语句| 循环语句} [end] <输出语句>::=prn 表达式 --注1：若if语句、else语句、循环语句中出现begin，后面的end 必须出现，即begin与end同对出现 --注2：if、while后的"（"，"）"表示终结符，而不是定义成分优先的说明符号 2、分析表： : = 变量常量，；运算 （) 符 变量 定义->②->②->②->② 赋值 语句->③->③->③->③-> ③ 条件 第四章语法分析—自上而下分析 知识结构： 带回溯分析法 回溯 自上而下分析面临的问题 左递归 问题的解决 语法分析－求FIRST、FOLLOW集合的算法自上而下分析LL(1)分析法证明LL(1)文法 构造LL(1)分析表 递归子程序的构造思想 递归子程序法递归子程序的特点 递归子程序的设计 第一节语法分析综述 一、语法分析的任务 按照语言即定的语法规则，对字符串形式的源程序进行语法检查，并识别出相应的语法成分。即语法结构是否符合语法规则。 二、语法分析器在编译程序中的地位（一遍扫描） 三、语法分析方法 通常把语法分析方法分为两大类，既自上而下分析与自下而上分析。 1、自上而下分析方法 实际上是一种产生的方法，分析过程是一个推导过程。 ⑴自上而下分析过程 从文法G的开始符号S出发，通过反复使用产生式，逐步推导出与输入的符号串完全相匹配的句子。采用最左推导，以文法开始符号为根结点，逐步为输入串自上而下地构造一棵语法树。 面临的输入符号为a，A所有的产生式： A12n ①若a FISRT(i)，则指派去执行匹配任务。 ②若a不属于任何一个候选首字符集，则： a、若属于某个FISRT(i)且a FOLLOW(A)，则让A 与自动匹配； b、否则，a的出现是一种错误。 例：设有文法G和输入符号串W：a*a+a G：S aA a A BaA B +-*/ 推导过程： S aA aBaA a*aA a*aBaA a*a+aA a*a+a=W 构造语法树： S a A B a A * B a A + ⑵自上而下分析法 自上而下分析法又可分为确定和不确定的两种。 ①不确定的分析法（带回溯） 是一种穷举的试探方法，效率低、代价高，极少使用。 ②确定的分析法（不带回溯） 实现方法简单、直观，便于手工构造或自动生成语法分析器，是目前常用的方法之一。但是对文法有一定的限制。 2、自下而上分析法 ⑴自下而上分析过程 分析过程是归约过程。从给定的输入串W开始，不断寻找与文法G中某个产生式P的侯选式（右部）进行匹配，并用P代替也称为归约。 ⑵自下而上分析法 #include"status_stack.h" #include"symbol_instr_stack.h" #include"lr.h" //打印LR分析器的工作过程 void print(status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p) { int i; out_stack(status_p); for(i=0;i<20-status_p->top;i++) printf(" "); out_stack1(symbol_p); for(i=0;i<20;i++) printf(" "); out_stack2(instr_p); printf("\n"); } //状态转换函数 int goto_char(status *status_p,symbol_instr *instr_p) { char x; int y,z; x = get_top(instr_p); y = get_top(status_p); z = get_index_char(x); return table[y][z]; } //移进－－规约函数 void action(status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p) { int i,j,x; char a; i = goto_char(status_p,instr_p); //规约出错 if(i == -1) printf("\n===============规约出错!================\n"); //规约成功 if(i == 12) printf("\n===============规约成功!================\n"); //移进动作 if(i>=0 && i<=11) { push(status_p,i); a = pop(instr_p); push(symbol_p,a); 语法分析器(含完整源 码) 语法分析实验报告 一、实验目的： 1. 了解单词(内部编码)符号串中的短语句型结构形成规律。 2. 理解和掌握语法分析过程中语法分析思想(LL，LR)的智能算法化方法。 二、实验内容： 构造自己设计的小语言的语法分析器： 1. 小语言的语法描述(语法规则)的设计即文法的设计； 2. 把文法形式符号中所隐含的信息内容挖掘出来并用LL或LR 的资料形式(分析表)表示出来； 3. 语法分析的数据输入形式和输出形式的确定； 4. 语法分析程序各个模块的设计与调试。 主要设备和材料：电脑、winxp操作系统、VC语言系统 三、实验分工： 081 四、实验步骤： 1、语法规则 ①<程序>::= {<变量定义语句>|<赋值语句>|<条件语句> |<循环语句> } ②<变量定义语句>::=var 变量{，变量}； ③<赋值语句>::=变量：= <表达式>； ④<表达式>::=标识符{运算符标识符}； ⑤<标识符>::=变量|常量 ⑥<运算符>::=+ | - | * | / | >= | <= ⑦<条件语句>::= 第四章语法分析——自上而下分析 【关键问题】 ◇什么叫确定的自上而下语法分析？ ◇自上而下语法分析是从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。 ◇在确定的自上而下语法分析过程中，当以同一个非终结符为左部的产生式有多个不同右部时，如何选择用哪个产生式的右部替换当前的非终结符？ ◇确定的自上而下语法分析对文法有何限制？ 【学习目标】 确定的自上而下分析方法虽对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。 ◇能够对一个给定的文法判断是否是LL(1)文法； ◇能构造预测分析表； ◇能用预测分析方法判断给定的输入符号串是否是该文法的句子； ◇能对某些非LL(1)文法做等价变换： ①消除左递归； ②提取左公共因子 【学习指南】 确定的自上而下分析由于实现方法简单、直观、便于手工构造，因此，仍是目前常用的语法分析方法之一，尤其对小型编译器的实现较为适合。确定的自上而下分析要求文法是LL(1)的，所以，能否用确定的自上而下分析方法构造语法分析器，首先必须对所给文法进行判断。由此构造LL(1) 分析器的关键问题是对文法的LL(1)判别。判断LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符的后跟符号集合（FOLLOW集）的计算。本章的学习要求大家对给定的文法能熟练、准确地计算出产生式右部符号串的开始符号集合和每个非终结符的后跟符号集合，只有这两个集合的元素计算准确无误，才能对LL(1)文法的判断得出正确结论，从而正确构造LL(1)分析表。对非LL(1)文法的等价变换特别要注意的是：消除了左递归、提取了左公共因子后不一定就能满足LL(1)文法的条件。 【难重点】 语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自上而下分析和自下而上分析两大类。本章将主要介绍确定的自上而下分析思想和对文法的要求。确定的自上而下分析要求文法满足LL(1)文法。本章主要介绍内容为： ◇LL(1) 文法的定义和判别 ◇非LL(1)文法的等价变换 ◇确定的自上而下分析方法 ◇预测分析方法 重点: ①LL(1)文法的定义和判别 ②非LL(1)文法的等价变换 ③预测分析方法 难点: 对一个文法如何判断是否是LL(1)文法。在判断LL(1)文法时用到文法符号串的开始符号集合（FIRST 集）和非终结符后跟符号集合（FOLLOW集）的计算，由于概念不清或不够细心常常导致对这两个集合的计算出错。 【知识结构】 编译原理-词法分析器的设计 一．设计说明及设计要求 一般来说，编译程序的整个过程可以划分为五个阶段：词法分析、语法分析、中间代码生成、优化和目标代码生成。本课程设计即为词法分析阶段。词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号）。如保留字（关键字或基本字）、标志符、常数、算符和界符等等。 二．设计中相关关键字说明 1．基本字：也称关键字，如C语言中的 if , else , while , do ,for,case,break, return 等。 2．标志符：用来表示各种名字，如常量名、变量名和过程名等。 3．常数：各种类型的常数，如12，6.88，和“ABC” 等。 4．运算符：如 + ，- , * , / ,%, < , > ,<= , >= 等。5．界符，如逗点，冒号，分号，括号，# ，〈〈，〉〉等。 三、程序分析 词法分析是编译的第一个阶段，它的主要任务是从左到右逐个字符地对源 程序进行 扫描，产生一个个单词序列，用以语法分析。词法分析工作可以是独立的一遍，把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件做为语法分析程序的输入而继续编译过程。然而，更一般的情况，常将 词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每得到一次调用，便从源程序文件中读入一些字符，直到识别出一个单词，或说直到下一个单词的第一个字符为止。 四、模块设计 下面是程序的流程图 五、程序介绍 在程序当前目录里建立一个文本文档，取名为infile.txt,所有需要分析的程序都写在此文本文档里，程序的结尾必须以“@”标志符结束。程序结果输出在同一个目录下，文件名为outfile.txt，此文件为自动生成。本程序所输出的单词符号采用以下二元式表示：（单词种别，单词自身的值）如程序输出结果(57,"#")(33,"include")(52,"<")(33,"iostream") 等。 程序的功能：（1）能识别C语言中所有关键字（共32个）（单词种别分别为1 — 32 ，详情见程序代码相关部分，下同） （2）能识别C语言中自定义的标示符（单词种别为 33） （3）能识别C语言中的常数（单词种别为0） （4）能识别C语言中几乎所有运算符（单词种别分别为41 — 54） （5）能识别C语言中绝大多数界符（单词种别分别为 55 — 66）六、运行结果 输入文件infile.txt 运行结果（输出文件 outfile.txt） 七、设计体会 八、附录部分（程序代码） 第四章自顶向下语法分析方法 语法分析是编译过程的核心部分。语法分析的任务是：按照文法，从源 程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序称为分析程序。也称为语法分析器，它是编译程序的主要子程序之一。 在第二章中我们已经介绍过。通过语法分析可建立起相应的语法树。按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。下面，我们先介绍自顶向下分析。 本章重点：自顶向下分析、LL（1）分析 第一节自顶向下分析方法 一、带回溯的自顶向下分析算法 这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。 下面用一个简单例子来说明这种过程： 假定有文法G[S] ： S—c A d A — ab|a 以及输入串w=cad 为了自上而下地构造w的语法树，我们首先按文法的识别符号产生根结点S, 并让指示器IP 指 向输入串的第一符号c。然后，用S的规则（此处左部为S的规则仅有一条）把这棵树发展为| （a） （b）（c） 图3-1-1 图3-1-1a。我们希望用S的子结从左至右匹配整个输入串w。首先，此树的最左子结是终结符c为标志的子结，它和输入串的第一个符号相匹配。于是，我们就把IP调整为指向下一输入符号a,并让第二个子结A去进行匹配，非终结符A有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b。子树A的最左子结和IP所指的符号相符，然后我们再把IP调为指向下一符号d并让A的第二个子结进入工作。但A 的第二个子结为终结符号b，与IP当前指的符号d不一致。因此，A宣告失败。这意味着A的第一个选择此刻不适用于构造w的语法树。这时，我们应该回头（回溯）看A是否还有别的选择。 为了实现回溯，我们一方面应把A的第一个选择所生长的子树注销掉；另一方面，应把IP恢复为进入A时的原值，也就是让它重新指向第二输入符号a。现在我们试探用A的第二个选择，即考虑生成图3-1-1C的语法树。 由于子树A只有一个子结a，而且，它和IP所指的符号相一致，于是，A ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1．对文法G[S] G: S →a | ∧| (T) T →T , S | S (1) 给出(a,(a,a))和(((a,a), ∧,(a)),a)的最左推导。 (2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3) 经改写后的文法是否是LL(1)的？给出它的预测分析表。 (4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 1. [解答] （1）①S ②S （T ）( T ) T , S T , S ②S=>(T) =>(T,S) =>(S,S) S ( T ) S a =>((T),S) =>((T,S),S) a T , S ( T ) =>((T,S,S),S) =>((S,S,S),S) S a T , S =>(((T),S,S),S) =>(((T,S),S,S),S) a T , S ( T ) =>(((S,S),S,S),S) =>(((a,S),S,S),S) ①S=>(T) =>(T,S) S ^ S =>(((a,a),S,S),S) =>(S,S) =>(a,S) =>(((a,a),^,S),S) =>(a,(T)) ( T ) a =>(((a,a),^,(T)),S) =>(a,(T,S)) =>(((a,a),^,(S)),S) =>(a,(S,S)) T , S =>(((a,a),^,(a)),S) =>(a,(a,S)) =>(((a,a),^,(a)),a) =>(a,(a,a)) S a a (2) 消除左递归 G': S→a | ∧| (T) T→ST' T'→,ST' |ε 递归子程序： program parser proceduce T; begin begin getsym; if sym in [a,^,() then S begin end; S; 第四章 自顶向下语法分析方法 语法分析是编译过程的核心部分。语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序称为分析程序。也称为语法分析器，它是编译程序的主要子程序之一。 在第二章中我们已经介绍过。通过语法分析可建立起相应的语法树。按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。下面，我们先介绍自顶向下分析。 本章重点：自顶向下分析、LL （1）分析 第一节 自顶向下分析方法 一、带回溯的自顶向下分析算法 这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。 下面用一个简单例子来说明这种过程： 假定有文法G[S]： S→c Ａd A →ab|a 以及输入串w=cad 为了自上而下地构造w 的语法树，我们首先按文法的识别符号产生根结点S ，并让指示器IP 指 c S 的规则仅有一条）把这棵树发展为 （ a ） （b ） （c ） 图3-1-1 图3-1-1a 。我们希望用S 的子结从左至右匹配整个输入串w 。首先，此树的最左子结是终结符c 为标志的子结，它和输入串的第一个符号相匹配。于是，我们就把IP 调整为指向下一输入符号a ，并让第二个子结A 去进行匹配，非终结符A 有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b 。子树A 的最左子结和IP 所指的符号相符，然后我们再把IP 调为指向下一符号d 并让A 的第二个子结进入工作。但A 的第二个子结为终结符号b ，与IP 当前指的符号d 不一致。因此，A 宣告失败。这意味着A 的第一个选择此刻不适用于构造w 的语法树。这时，我们应该回头（回溯）看A 是否还有别的选择。 为了实现回溯，我们一方面应把A 的第一个选择所生长的子树注销掉；另一方面，应把IP 恢复为进入A 时的原值，也就是让它重新指向第二输入符号a 。现在我们试探用A 的第二个选择，即考虑生成图3-1-1c 的语法树。 由于子树A 只有一个子结a ，而且，它和IP 所指的符号相一致，于是，A 完成了匹配任务。在A 获得匹配后，指示器指向下一个未被触及的符号d 。 在S 的第二子结A 完成匹配后，接着就轮到第三个子结d 进行工作。由于这个子结和最后一个输入符号相符，于是，我们完成了构造语法树的任务，证明了w 是文法G[ s]的一个句子。 上述自顶向下地为输入符号w 建立语法树的过程，实际上也是设法建立一个最左推导序列，以便通过一步步推导将输入串推导出来。很明显，对于输入串w 可以通过如下的推导过程将其推导出来：S ?CAd ?cad 所以用最左推导，是因为我们对输入串是自左向右扫描的，只有使用最左推导，才能保证按扫描顺序去匹配输入串。在上述推出符号串w 的过程中，由于出现在符号串中的非终结符号只有一个，因此，未明显地表现出最左推导的性质。 根据以上分析，不难编出程序来实现这种分析的算法。但是，上述这种自顶向下的分析算法存语法分析(自上而下分析)实验报告
四川大学Cminus语法分析器纯代码
语法分析器源代码
编译原理词法分析和语法分析报告+代码(C语言版)
【习题答案】第05章 自底向上的语法分析
语法分析C语言程序
语法分析代码
编译原理 LL(1)语法分析器java版 完整源代码
第五章 自上而下语法分析
语法分析器(完整代码)1
语法分析-自上而下分析
语法分析代码2(LR分析器 C语言实现)
语法分析器(含完整源码)教学文稿
第四章 语法分析——自上而下分析
编译原理课程设计-词法分析器(附含源代码)
编译原理-四章自顶向下语法分析法
习题与答案-5-语法分析-自上而下
编译原理 第四章自顶向下语法分析法
相关文档
- 编译原理实验2-自底向上语法分析算法程序设计
- 自底向上语法分析
- 编译原理 自顶向下语法分析方法
- 第六章自底向上语法分析
- 第五章语法自底向上方法介绍
- 第五章 语法分析-自底向上分析方法
- 第6章 自底向上分析思想
- 第六章 自底向上优先分析(编译原理)
- 【习题答案】第05章 自底向上的语法分析
- 编译原理-四章自顶向下语法分析法
- 自底向上分析
- 自底向上的语法分析
- 编译原理-清华大学-第5章-自底向上优先分析法(2+1)
- 第五章 自底向上语法分析
- 编译原理 4.2自底向上的语法分析(3)
- 编译原理_05自底向上的语法分析方法
- 编译原理自底向上优先分析法
- 自底向上分析
- 自底向上的语法分析
- 编译原理自底向上语讲义法分析