自上而下语法分析器设计习题1

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 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 aa(2) 消除左递归G': S→a | ∧| (T)T→ST'T'→,ST' |ε递归子程序：program parser proceduce T;begin begingetsym; if sym in [a,^,() thenS beginend; S;proceduce S; T;begin end;if sym=’a’ or sym=’^’ then elsegetsym error;elseif sym=’(‘ end;begin getsym; proceduce T’;T; beginIf sym=’)’ then if sym=’,’ thenGetsym; beginElse getsym;Error; S;End; T;Else end;Error; elseEnd; if sym=’)’ thenelseerror;end;预测分析表不含多重定义入口, 所以该文法是LL(1)文法!(4) 分析栈余留串所用产生式或动作1 #S (a,a)# S—>(T)2 #)T( (a,a)# (匹配3 #)T a,a)# T—>ST’4 #)T’S a,a)# S—>a5 #)T’a a,a)# a匹配6 #)T’ ,a)# T’ —>,ST’7 #)T’S, ,a)# ,匹配8 #)T’S a)# S—>a9 #)T’a a)# a匹配10 #)T’ )# T’—>ε11 #) )# )匹配12 # # 接受因为（a,a）#分析成功所以（a,a）为文法的句子步骤分析栈余留串所用产生式或动作1 #S (a,a# S→(T)2 #)T( (a,a# ( 匹配3 #)T a,a# T→ST’4 #)T’S a,a# S→a5 #)T’a a,a# a 匹配6 #)T’,a# T’→,ST’7 #)T’S, ,a# , 匹配8 #)T’S a# S→a9 #)T’a a# a 匹配10 #)T’# 出错^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 2. G: E →TE'E' →+E |εT →FT'T' →T |εF →PF'F' →*F' |εP →(E) | a | b |∧预测分析表^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 3．已知文法G: S →MH | aH →LSo |εK →dML |εL →eHfM →K | bLM判断G是否是LL(1)文法，如果时，构造LL(1)分析表。

实验5---语法分析器（自下而上）：LR(1)分析法一、实验目的构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

二、实验内容程序输入/输出示例（以下仅供参考）：对下列文法，用LR（1）分析法对任意输入的符号串进行分析：（1）E->E+T（2）E->E—T（3）T->T*F（4）T->T/F（5）F-> (E)（6）F->i输出的格式如下：(1)LR（1）分析程序，编制人：姓名，学号，班级(2)输入一个以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串(3)输出过程如下：3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。

同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照。

三、实验方法1．实验采用C++程序语言进行设计，文法写入程序中，用户可以自定义输入语句；2．实验开发工具为DEV C++。

四、实验步骤1．定义LR(1)分析法实验设计思想及算法①若ACTION[sm , ai] = s则将s移进状态栈，并把输入符号加入符号栈，则三元式变成为：(s0s1…sm s , #X1X2…Xm ai , ai+1…an#)；②若ACTION[sm , ai] = rj则将第j个产生式A->β进行归约。

此时三元式变为(s0s1…sm-r s , #X1X2…Xm-rA , aiai+1…an#)；③若ACTION[sm , ai]为“接收”，则三元式不再变化，变化过程终止，宣布分析成功；④若ACTION[sm , ai]为“报错”，则三元式的变化过程终止，报告错误。

2．定义语法构造的代码，与主代码分离，写为头文件LR.h。

3．编写主程序利用上文描述算法实现本实验要求。

五、实验结果1. 实验文法为程序既定的文法，写在头文件LR.h中，运行程序，用户可以自由输入测试语句。

1.课程设计目的：1.1 设计目的：通过编程实现语法分析（自上而下，自下而上）的可视化过程，加深对两法分析原理思想的理解。

[目的要求]通过设计编制调试一个具体的语法分析程序，加深对语法分析原理的理解。

并掌握在对程序设计语言源程序进行扫描过程中将其进行语法分析的方法。

[题目分析]递归下降分析方法是一种确定的自上而下分析方法。

它的基本思想是给文法的每一个非终结符均设计一个相应的子程序。

由于文法的产生式往往是递归的，因为这些子程序往往也是递归的。

1.2 开发环境：操作系统：Windows XP辅助工具：Visual Studio 2008编程语言：C#2. 课程设计要求（1）选定一文法，选定一种分析方法（自上而下、自下而上）（2）允许用户输入语句并对该语句进行相应的语法分析（3）要求显示语法树的建立过程以及跟踪分析表和分析栈的状态（4）要提供单步运行，让用户跟踪分析器工作的每一个步骤。

3. 总体设计3.1 设计框架:3.2 程序流程图：4. 设计功能描述：（1）该课程设计对语法分析指定了固定的文法,运行界面为:“开始”，会出现提示：。

（3）用户输入字符串，可以点击“”，软件根据该输入字符串做好初始化工作，再点击“”，开始分析，每一次点击“下一次”，就做分析的一个步骤，并且此时分析栈和输入栈做相应的出栈、入栈的的动作，同时在“分析栈”，“输入栈”，“输出栈”会显示出相应的状态。

（4）分析结果显示在中（5）如果在分析完后，还需要继续输入字符串分析的画，点击“”，可以再次作上述的操作。

（6）如果想退出程序，点击““，此时会弹出提示窗口：，点击“确定”，便退出程序。

分析实例：输入分析的字符串为i*（i+i）结果如下：5. 源程序代码：#region相关初始量(都是全局的)public string[] mystring = { "TC", "FALSE", "FALSE", "TC", "FALSE", "FALSE", "FALSE", "+TC", "FALSE", "FALSE", "ε", "ε", "FD", "FALSE", "FALSE", "FD", "FALSE", "FALSE", "FALSE", "ε", "*FD", "FALSE", "ε", "ε", "i", "FALSE", "FALSE", "(E)", "FALSE", "FALSE" };//分析表数组bool con = true;//控制显示的布尔量private Stack MyStack = new Stack(); //申请一个分析栈private Stack MyInputstack = new Stack();//申请一个输入栈public string[] Term = { "i", "+", "*", "(", ")", "&" }; //终结符数组public string[] unTerm = { "E", "C", "T", "D", "F" };//非终结符数组private int line, row; //定义行，列的全局变量string MyNowString;#endregion“开始”按钮实现的函数private void开始_Click(object sender, EventArgs e){if (Input_richTextBox1.Text == ""){MessageBox.Show("请输入要分析的字符串！");}else{this.MyOutput_listBox3.Items.Add("");MyStack.Push("&");MyStack.Push("E");MyStack_listBox1.Items.Add("&E");MyInput_listBox2.Items.Add(Input_richTextBox1.Text + "&");MyInputstack.Push("&");for (int i = Input_richTextBox1.Text.Length - 1; i >= 0; i--){MyInputstack.Push(Input_richTextBox1.Text[i]);}begin.Enabled = false;}}#region“下一步”按钮实现的函数private void下一步_Click(object sender, EventArgs e){int loc;string MyStackTop, MyStackInputTop;MyStackTop = MyStack.Peek().ToString();MyStackInputTop = MyInputstack.Peek().ToString();MyStackTopOne(MyStackTop);if (MyStackTopOne(MyStackTop)){MyStackTopTwo(MyStackTop, MyStackInputTop);}else if (MyStackTopThree(MyStackTop) &&MyInputStackTopOne(MyStackInputTop)){loc = line * 6 + row;MyNowString = mystring[loc];this.MyOutput_listBox3.Items.Add(MyStack.Peek().ToString() + "-->" + mystring[loc]);Analyse();}else{Rezult_richTextBox2.Text = "分析出错!";nextStep.Enabled = false;con = false;}if (con){ShowMyStack();ShowMyInpuStack();}}#endregion#region显示分析栈里的字符private void ShowMyStack(){string ch = "";int len = MyStack.Count;string display = "";for (int i = 0; i < len; i++){string t;t = MyStack.Pop().ToString();display = display + t;}for (int i = len - 1; i >= 0; i--){ch = ch + display[i];MyStack.Push(display[i]);this.MyStack_listBox1.Items.Add(ch);}#endregion#region显示输入栈里的字符private void ShowMyInpuStack(){int len = MyInputstack.Count;string display = "";for (int i = 0; i < len; i++){string t;t = MyInputstack.Pop().ToString();display = display + t;}for (int i = len - 1; i >= 0; i--){MyInputstack.Push(display[i]);}this.MyInput_listBox2.Items.Add(display);}#endregion#region判断状态栈栈顶元素是否为终结符public bool MyStackTopOne(string stack){bool symbol = false;for (int i = 0; i < Term.Length; i++){if (stack == Term[i]){symbol = true;break;}}return symbol;}#endregion#region状态栈栈顶元素是终结符的处理方法private void MyStackTopTwo(string stack, string input) {if (stack == input)if (stack == "&"){Rezult_richTextBox2.Text = "分析成功!"; nextStep.Enabled = false;con = false;}else{MyStack.Pop();MyInputstack.Pop();this.MyOutput_listBox3.Items.Add(""); }}}#endregion#region返回状态栈栈顶元素在非终结符数组里的下标public bool MyStackTopThree(string stack){bool symbol = false;for (int i = 0; i < unTerm.Length; i++){if (unTerm[i] == stack){line = i;symbol = true;break;}}return symbol;}#endregion#region返回输入栈栈顶元素在终结符数组里的下标private bool MyInputStackTopOne(string myinput){bool symbol = false;for (int i = 0; i < Term.Length; i++){if (Term[i] == myinput){row = i;symbol = true;break;}return symbol;}#endregion#region分析表字符入栈private void Analyse(){if (MyNowString == "FALSE"){Rezult_richTextBox2.Text = "分析出错!";nextStep.Enabled = false;con = false;}else if (MyNowString == "ε"){MyStack.Pop();}else{MyStack.Pop();for (int i = MyNowString.Length - 1; i >= 0; i--) {MyStack.Push(MyNowString[i]);}}}#endregion#region“退出”按钮实现的函数private void exit_button2_Click(object sender, EventArgs e) {DialogResult ret;ret = MessageBox.Show("确定要退出吗？","退出",MessageBoxButtons.OKCancel,MessageBoxIcon.Question,MessageBoxDefaultButton.Button2);if (ret == DialogResult.OK){this.Close();}}#endregion#region“重置”按钮实现的功能private void clear_Button_Click(object sender, EventArgs e){Input_richTextBox1.Clear();Rezult_richTextBox2.Clear();this.MyStack_listBox1.Items.Clear();this.MyInput_listBox2.Items.Clear();this.MyOutput_listBox3.Items.Clear();MyStack.Clear();MyInputstack.Clear();begin.Enabled = true;nextStep.Enabled = true;con = true;}#endregionprivate void button1_Click(object sender, EventArgs e){pictureBox1.Visible = true;}}6. 总结:通过本次课程设计，对于语法分析的原理与方法有了进一步的体会，在通过使用visual studio 2008的同时让我们对c#和语法分析有了更深的理解。

1．★已知文法G[S]：S→SaA|AA→AbB|BB→cSd|e请证实AacAbcBaAdbed是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。

符号栈S 关系输入串最左素短语S1 S2 S3 S4 S5 S6 S7 R1 R2 R3 R4 R5 R6＃< ( a d b ) ##<( < a d b ) ##<(< a > d b ) # d#<( V < d b ) ##<( V<d < b ) ##<( V<d<b > ) # b#<( V<d V > ) # VdV#<( V = ) ##<( =V ) > # (V)# V # 接受因为存在从文法开始符号S到符号串AacAbcBaAdbed的推导过程（如图6.1中的语法树所示），所以符号串AacAbcBaAdbed是文法的句型。

从图6.1中句型A1a1c1 A2b1c2Ba2 A3d1b2ed2的语法树可知，该句型的短语有：A1、B、Ba2 A3、c2Ba2 A3d1、A2b1c2Ba2 A3d1、e、A2b1c2Ba2 A3d1b2e、c1 A2b1c2Ba2 A3d1b2ed2、A1a1c1 A2b1c2Ba2 A3d1b2ed2该句型的素短语有：Ba2 A3、e该句型的句柄为：B2．★已知文法G[S]：S→*AA→0A1|*（1）求文法G的各非终结符号的FIRSTVT集和LASTVT集;（2）构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法；（3）分析句子*0*1，并写出分析过程。

解：本题考查算符优先分析法中的有关知识：非终结符号的FIRSTVT集和LASTVT集的求法、算符优先关系的构造、算符优先文法的定义、算符优先分析过程等。

（1）求文法G的各非终结符号的FIRSTVT集和LASTVT集。

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 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 aa(2) 消除左递归G': S→a | ∧| (T)T→ST'T'→,ST' |ε递归子程序：program parser proceduce T;begin begingetsym; if sym in [a,^,() thenS beginend; S;proceduce S; T;begin end;if sym=’a’ or sym=’^’ then elsegetsym error;elseif sym=’(‘ end;begin getsym; proceduce T’;T; beginIf sym=’)’ then if sym=’,’ thenGetsym; beginElse getsym;Error; S;End; T;Else end;Error; elseEnd; if sym=’)’ thenelseerror;end;LL(1)文法!(4) 分析栈余留串所用产生式或动作1 #S (a,a)# S—>(T)2 #)T( (a,a)# (匹配3 #)T a,a)# T—>ST’4 #)T’S a,a)# S—>a5 #)T’a a,a)# a匹配6 #)T’ ,a)# T’ —>,ST’7 #)T’S, ,a)# ,匹配8 #)T’S a)# S—>a9 #)T’a a)# a匹配10 #)T’ )# T’—>ε11 #) )# )匹配12 # # 接受因为（a,a）#分析成功所以（a,a）为文法的句子步骤分析栈余留串所用产生式或动作1 #S (a,a# S→(T)2 #)T( (a,a# ( 匹配3 #)T a,a# T→ST’4 #)T’S a,a# S→a5 #)T’a a,a# a 匹配6 #)T’,a# T’→,ST’7 #)T’S, ,a# , 匹配8 #)T’S a# S→a9 #)T’a a# a 匹配10 #)T’# 出错^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 2. G: E →TE'E' →+E |εT →FT'T' →T |εF →PF'F' →*F' |εP →(E) | a | b |∧预测分析表^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 3．已知文法G: S →MH | aH →LSo |εK →dML |εL →eHfM →K | bLM判断G是否是LL(1)文法，如果时，构造LL(1)分析表。

1.设有文法G[S]：S→ABA→bB|AaB→Sb|a试消除该文法的左递归。

解：本题考查消除左递归的方法。

应用消除文法左递归的算法对文法G[S]消除左递归的过程如下：（1）将非终结符排序为：U1=S，U2=A，U3=B（2）进入算法排序：i=1时，对文法无影响i=2，j=1时：A→Aa有直接左递归，消去该直接左递归，得A→bBA’A’→aA’|εi=3，j=1时：改写文法，有B→ABb|aj=2时：改写文法，有B→bBA’Bb|a无左递归。

（3）所以文法G[S]消除左递归后变为：G’[S]：S→ABA→bBA’A’→aA’|εB→bBA’Bb|a2.设有文法G[E]:E→Aa|BbA→cA|eBB→bd试按照递归子程序法为该文法构造语法分析程序。

解：本题考查递归子程序的构造方法。

首先判断文法是否满足递归子程序法对文法的要求，然后再构造递归子程序。

因为：（1）该文法无左递归。

（2）文法的产生式E→Aa|Bb和A→cA|eB的右部有若干选项，判断这两条产生式右部各候选式的终结首符号集合是否两两互不相交。

对产生式E→Aa|Bb，有FIRST(Aa)∩FIRST(Bb)={c，e}∩{b}=ø对产生式A→cA|eB，有FIRST(cA)∩FIRST(eB)={c}∩{e}=ø文法中其他产生式都只有一个非空ε的右部。

综合（1）、（2），该文法可以采用自上而下分析方法进行语法分析而不会出现回朔和无限循环。

下面为该文法的每一个非终结符号构造递归子程序。

假设用READAWORD代表读下一个单词。

用P(E)、P(A)、P(B)分别表示非终结符号E、A、B对应的子程序名。

约定输入符号串以“#”作为输入结束符。

P(E)的递归子程序为：PROCEDURE P(E);BEGINIF WORD IN FIRST(Aa)THENBEGINP(A);READAWORD;IF WORD=’a’THEN READAWORDELSE ERRORENDELSE IF WORD IN FIRST(Bb)THENBEGINP(B);READAWORD;IF WORD=’b’THEN READAWORDELSE ERRORENDELSE ERROREND;P(A)的递归子程序为：PROCEDURE P(A);BEGINIF WORDD=’c’THENBEGINREADAWORD;P(A)ENDELSE IF WORD=’e’THENBEGINREADWORD;P(B)ENDELSE ERROREND;P(B)的递归子程序为：PROCEDURE P(B);BEGINIF WORD=’b’THENBEGINREADAWORD;IF WORD=’d’THEN READAWORDELSE ERRORENDELSE ERROREND;主程序中的主要内容为：READAWORD;P(E);IF WORD=”#”THEN WRITE(“RIGHT!”)ELSE WRITE(“ERROR!”)3.已知文法G[E]：G[E]：E→E+T|TT→T*F|FF→i|(E)请按递归子程序法为其构造语法分析程序。

实习二语法分析－自上而下分析一、实验目的使用预测分析方法对输入的表达式进行分析，掌握其具体的使用并且学会去分析一个文法。

二、实验内容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<stdio.h>#include<stdlib.h>#include<string.h>#include<dos.h>char A[20];char B[20];char v1[20]={'i','+','*','(',')','#'};/*终结符*/char v2[20]={'E','G','T','S','F'};/*非终结符*/int j=0,b=0,top=0,l;/*L为输入串长度*/typedef struct type{char origin;/*大写字符*/char array[5];/*产生式右边字符*/int length;/*字符个数*/}type;type e,t,g,g1,s,s1,f,f1;/*结构体变量*/ type C[10][10];/*预测分析表*/void print()/*输出分析栈*/{int a;/*指针*/for(a=0;a<=top+1;a++)printf("%c",A[a]);printf("\t\t");}/*print*/void print1()/*输出剩余串*/{int j;精选文库for(j=0;j<b;j++)/*输出对齐符*/printf(" ");for(j=b;j<=l;j++)printf("%c",B[j]);printf("\t\t\t");}/*print1*/void main(){int m,n,k=0,flag=0,finish=0;char ch,x;type cha;/*用来接受C[m][n]*//*把文法产生式赋值结构体*/e.origin='E';strcpy(e.array,"TG");e.length=2;t.origin='T';strcpy(t.array,"FS");t.length=2;g.origin='G';strcpy(g.array,"+TG");g.length=3;精选文库g1.origin='G';g1.array[0]='^';g1.length=1;s.origin='S';strcpy(s.array,"*FS");s.length=3;s1.origin='S';s1.array[0]='^';s1.length=1;f.origin='F';strcpy(f.array,"(E)");f.length=3;f1.origin='F';f1.array[0]='i';f1.length=1;for(m=0;m<=4;m++)/*初始化分析表*/for(n=0;n<=5;n++)C[m][n].origin='N';/*全部赋为空*//*填充分析表*/C[0][0]=e;C[0][3]=e;C[1][1]=g;C[1][4]=g1;C[1][5]=g1;C[2][0]=t;C[2][3]=t;C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1;C[4][0]=f1;C[4][3]=f;printf("请输入要分析的字符串:");do/*读入分析串*/{scanf("%c",&ch);if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#')){printf("输入串中有非法字符\n");exit(1);}B[j]=ch;j++;}while(ch!='#');l=j;/*分析串长度*/ch=B[0];/*当前分析字符*/A[top]='#'; A[++top]='E';/*'#','E'进栈*/printf("步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n");do{x=A[top--];/*x为当前栈顶字符*/ printf("%d",k++);printf("\t\t");for(j=0;j<=5;j++)/*判断是否为终结符*/ if(x==v1[j]){flag=1;break;}if(flag==1)/*如果是终结符*/{if(x=='#'){finish=1;/*结束标记*/printf("acc!\n");/*接受*/getchar();getchar();exit(1);}/*if*/if(x==ch){print();print1();printf("%c匹配\n",ch);ch=B[++b];/*下一个输入字符*/flag=0;/*恢复标记*/}/*if*/else/*出错处理*/{print();print1();printf("%c出错\n",ch);/*输出出错终结符*/exit(1);}/*else*/}/*if*/else/*非终结符处理*/{for(j=0;j<=4;j++)if(x==v2[j]){m=j;/*行号*/break;}for(j=0;j<=5;j++)if(ch==v1[j]){n=j;/*列号*/break;}cha=C[m][n];if(cha.origin!='N')/*判断是否为空*/{print();print1();printf("%c->",cha.origin);/*输出产生式*/for(j=0;j<cha.length;j++)printf("%c",cha.array[j]);printf("\n");for(j=(cha.length-1);j>=0;j--)/*产生式逆序入栈*/ A[++top]=cha.array[j];if(A[top]=='^')/*为空则不进栈*/top--;}/*if*/else/*出错处理*/{print();print1();printf("%c出错\n",x);/*输出出错非终结符*/exit(1);}/*else*/}/*else*/}while(finish==0);}/*main*/。

编译原理习题作业⼀1.已知⽂法G[A]，写出它定义的语⾔描述如：G[A]:A → 0B|1CB → 1|1A|0BBC → 0|0A|1CC2. 给出⽣成下述语⾔的上下⽂⽆关⽂法：（1）{ a n b n a m b m| n，m>=0}(2) { 1n0m 1m0n| n，m>=0}3. 给出⽣成下述语⾔的三型⽂法：(1){ a n b m|n,m>=1 }(2){a n b m c k|n,m,k>=0 }4、⽂法G[E]为：E→E+T|TT→T*F|FF→(E)|i试给出句型(E+F)*i的短语，简单(直接)短语,句柄。

第3章练习题⼀、判断题:1、编译程序中的词法分析程序以字符形式的源程序作为输⼊，输出的单词符号常采⽤⼆元组的形式。

2、正规式的运算符“|”读作“或“。

3、若两个正规式所表⽰的正规集相同，则认为⼆者是等价的。

4、⽤l代表字母，d代表数字，Σ={l，d}，则正规式r=dd*定义了⽆符号整数单词。

5、⼀个确定的有穷⾃动机DFA M的转换函数f是⼀个从KⅹΣ到K 的⼦集的映像。

6、⼀个⾮确定的有穷⾃动机NFA N 的转换函数f是⼀个从KⅹΣ*到K 的映像。

7、⼀张状态转换图只包含有限个状态，其中有⼀个被认为是初态，最多只有⼀个终态。

8、终态与⾮终态是可区别的。

9、对任意⼀个右线性⽂法G，都存在⼀个NFA M，满⾜L（G）=L（M）。

10、对任意⼀个右线性⽂法G，都存在⼀个DFA M，满⾜L（M）=L（R）。

⼆、构造正规式1(0|1)*101相应的DFA.练习题2⼀、判断题：1、空符号串的集合{ε}={}=ф。

2、设A是符号串的集合，则A0=ε。

3、设G是⼀个⽂法，S是开始符号，如果S => x且x∈V T*,则称x是⽂法G[S]的句型。

4、在形式语⾔中，最右推导的逆过程也称为规范归约。

5、⼀个语⾔的⽂法是唯⼀的。

6、若⼀个语⾔是⽆穷集合，则定义该语⾔的⽂法⼀定是递归的。

实验三预测分析法判断算术表达式的正确性学时数：6一、实验目的1、理解语法分析器的构造方法和工作原理；2、理解自上而下语法分析方法；3、熟练掌握预测分析程序的构造方法。

二、实验内容算术表达式的文法是G[E]：E→E+T| TT→T*F| FF→(E)| id用预测分析法按文法G[E]对算术表达式（包括+、*、（）的算术表达式）进行语法分析，判断该表达式是否正确。

三、实验步骤1、准备：阅读课本有关章节，将上述算术表达式的文法改造成LL(1)文法；设计出预测分析表；按算法3.1（P56）编写程序。

2、上机调试，发现错误，分析错误，再修改完善。

四、测试要求1、为降低难度，表达式中不含变量（只含单个无符号整数或i）；2、如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3、测试用的表达式建议事先放在文本文件中，一行存放一个表达式，同时以分号结束。

同时将语法分析程序的输出结果写在另一个文本文件中；4、对学有余力的同学，可增加功能：当判断一个表达式正确时，输出计算结果。

5、程序输入/输出示例：如参考C语言的运算符。

输入如下表达式（以分号为结束）和输出结果：（a）1;输出：正确（b）1+2;输出：正确（c）(1+2)/3+4-(5+6/7);输出：正确（d）((1-2)/3+4输出：错误，缺少右括号（e）1+2-3+(*4/5)输出：错误五、实验报告要求1、写出修改后LL(1)文法，所构造的预测分析表。

2、通过对核心代码做注释或通过程序流程图的方式说明预测分析程序的实现思想。

3、写出调试程序出现的问题及解决的方法。

4、给出测试的结果。

六、思考（选作）文法G[E]所构造算术表达式只包含+和*。

请修改文法和程序，使得该语法程序可判断包含减号和除号的算术表达式的正确性。

[实验指导]将文法G[E]改造为LL(1)文法如下：G’[E]：E → TE’E’→ +TE’| εT → FT’T’→ *FT’|εF → (E)| i[补充说明]预测分析法分析程序可以从网上下载，但要求：（1）理解该程序，在实验报告中说明该程序所使用的文法和预测分析表；（2）实验报告要求同上。