下载文档原格式
编译原理-⾃顶向下的语法分析1.代替部分由公因⼦就会出现回溯。
2.LL(1)⽂法（1）FIREST集这样说从⽂法的左部找右部相关的⾮终结符号。
若 X->BC..D,则将First（B）所有元素（除了ε）加⼊First（A），然后检测First（B），若First（B）中不存在ε,则停⽌，若存在则向B的后⾯查看，将First（C）中所有元素（除了ε）加⼊First（A），然后再检测First（C）中是否有ε...直到最后，若D之前的所有⾮终结符的First集中都含有ε,则检测到D时，将First（D）也加⼊First（A），若First（D）中含有ε,则将ε加⼊First（A）。
（2）FOLLOW集：记住是从⽂法的右部去找的。
1）S是开始符号,将#放到follow（S）中. 2）存在A→αBβ（且β！=ε），那么first（β）中除ε之外的所有符号都在follow（B）中。
3）存在A→αB或A→αBβ（且first（β）包含ε），那么follow（A）中的所有符号都在follow（B）中。
（注意都没有说α⼀定存在。
）（3）SELECT集对于产⽣式A—>α。
集合select（A—>α）定义如下：1. 若α不能推出ε，则select（A—>α） = first（α）。
2. 若α能推出ε，则select（A—>α）= first（α）∪ follow(A)。
（4）如何判断⼀个⽂法是不是LL（1）⽂法：第⼀消除左递归，先消除去直接左递归，然后看是否有相同最左公因⼦的，提取出来。
第⼆分别求出每个推导的SELECT集，同⼀左部的求SELECT集的交集，所有的这种交集为空的话就是LL(1)⽂法，否则不是。
3.递归下降分析法：只针对LL(1)⽂法的，所以没有左递归。
简单的来说就是为每个⾮终结符号编写⼀个处理程序，⽽处理程序的代码结构是由相应的⾮终结符号的规则右部所决定。
p68.4.预测分析表的构造:p74。
本章在编译程序中的地位表词法分析器语法分析器源程序单词符号出2• 上下文无关文法的定义：G G=(V T V N S P)– V T ( )– V N ( ) V T ∩ V N =∅ – S S ∈V N– P ( )P →α P ∈V N α ∈ (V T ∪ V N )*– S复习• + *G= {i + * ( )} {E} E PPE → iE → E+EE → E*EE → (E)(i+i)E⇒(E)⇒(E+E)⇒(i+E)⇒(i+i)34},|{)(*TV S G L ∈⇒=+αααq 定义：假定G是一个文法，S 是它的开始符号。
如果Sα ，则α称是一个句型。
仅含终结符号的句型是一个句子。
文法G所产生的句子的全体是一个语言，将它记为 L(G)。
• α1 αn α1 αn+ ⇒α1 αn α1 0 αn* ⇒ 所以 ： α1 αn 即 α1=αn , α1 αn* ⇒ + ⇒ * ⇒第4章 自上而下语法分析• 消除文法左递归，消除回溯，计算FIRST集、FOLLOW集，LL(1)分析条件， LL(1)文法的概念，预测分析表的构造。
• ：自上而下分析方法的基本思想, 自上而下分析的过程。
• 4.14.24.3 LL(1)4.4重点难点4.5＊4.6 LL(1)564.1 语法分析器的功能• 是在词法分析识别出单词符号串的基础上，分析判断程序的 是否符合语法规则。
• 是编译过程的核心部分。
• 有自上而下和自下而上两类。
两种方法反映了两种语法树的构造过程。
74.1 语法分析器的功能• " " 推导。
也就是从文法的开始符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串.• “归约”也就是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树.注：这里所说的输入符号串指词法分析所识别的单词。
84.2 自上而下分析面临的问题• – . – .• 例4.1文法：⑴ S→xAy⑵ A→** ⑶ A→*输入串 α=x*y，分析α是否该文法的句子？指示器IP指向 语法树 最左推导 说明x*y S S, x序号 ip 指向 语法树 最左推导 说明S x*yx A y A →** AS ⇒xAy ⇒x**y* *x*y* , ip S序号 ip 指向 语法树 最左推导 说明x*y Sx A yA →* AS ⇒xAy ⇒x*y * x*y * , ip Sx A y12自上而下分析• 从文法的开始符号出发，向下推导，试图推出句子，匹配输入符号串，寻找输入串的最左推导，并按与最左推导相对应的顺序，自上而下从左到右地建立输入串的语法分析树。
编译原理武汉大学计算机学院编译原理课程组自上而下语法分析·基本思想·存在的问题·解决方法·LL(1)方法·递归子程序法消除左递归FIRST集、FOLLOW集·LL(1)文法递归子程序的构造LL(1)分析表的构造6.1 自下而上语法分析1．自下而上语法分析的基本思想从输入的符号串开始，利用文法的产生式步步向上归约，试图归约到文法的识别符号。
如果从语法树的角度看，自下而上分析的过程是以输入符号串作为末端结点符号串，向着根结点的方向往上构造语法树，使识别符号正好是该语法树的根结点。
相应于高级语言的编译过程，自下而上语法分析就是从该高级语言文法的源程序或与其等价的单词串出发，试图归约得到该文法的开始符号——<程序>。
6.1 自下而上语法分析3.自下而上语法分析遇到的基本问题例如，对文法G[S]：S→aAcBeA→bA→AbB→d分析符号串abbcde。
1．短语、直接短语与句柄6.2 短语和句柄则称句型xuy 中的子串u 为句型xuy (相对于非终结符号U )的短语。
设有文法G[Z]，w=xuy 是它的一个句型，如果有Z *⇒xUy +⇒且U u U ⇒u则称u为句型xuy的直接（简单）短语。
特别地，如果前述条件中U +⇒u为句型的最左直接（简单）短语称为句柄。
6.2 短语和句柄例：设有文法G[S]：S→ABA→Aa|bBB→a|Sb请给出句型baabaab的所有短语、直接短语和句柄。
6.2 短语和句柄2．短语、简单（直接）短语、句柄与语法树的关系语法树子树的末端结点符号串即是语法树所描述句型（相对于子树的根）的短语；简单子树（只有父子两代）的末端结点符号串即是直接短语。
最左简单子树的末端结点符号串即是句柄。
6.2 短语和句柄例：设有文法G[S]：S→ABA→Aa|bBB→a|Sb请给出句型baabaab的所有短语、直接短语和句柄。
第 6 章自学内容第 6 章作业P100 6.8求下列句型的所有短语、简单（直接）短语和句柄。
实验报告实验项目列表一、实验名称自顶向下语法分析方法的实现二、实验目的1.掌握自顶向下语法分析的方法；2.运用编程的手段实现自顶向下语法分析。
三、实验内容和要求四、实验环境1．硬件环境：PC机2．软件环境：Windows操作系统，VC++集成开发环境五、算法设计思想六、主要问题与解决方法七、实验结果以下是程序的用户运行界面截图：八、体会、质疑、建议九、源代码#include<fstream>#include<sstream>#include<iostream>#include<vector>#include<string>#include<windows.h>#include<iterator>#include<algorithm>#include<stdlib.h>#define M 20using namespace std;void gotoxy(int x,int y){COORD coord;coord.X=x;coord.Y=y;SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HANDLE ), coord );}class table{public:void read();friend class an_process;string find_str(char row,char col);private:string matrix[M][M];char start;vector<string> vec_row;vector<string> vec_col;};class sentence{public:void read_in();friend class an_process;private:string str_input;};class an_process{public:void analyse(const table LL1_table,const sentence input);void write_result();void print2(int x,int y);private:vector<int> step;vector<vector<char> > stack_note;vector<string> remain;vector<string> production;};void table::read(){string a,str;char x,y;int linenum = 0;char line[1024]={0};ifstream infile("table1.txt");if(!infile){cerr<<"错误！无法存储用户数据！\n";}while(infile.getline(line,sizeof(line))){stringstream word(line);if(linenum>1){if(word>>x&&word>>y&&word>>str){matrix[x-48][y-48]=str;/*cout<<x<<" ";cout<<y<<" ";cout<<matrix[x-48][y-48]<<" ";*/}}while(word>>a&&linenum<2){if(linenum==0){vec_col.push_back(a);/*cout<<a<<" ";*/}else if(linenum==1){vec_row.push_back(a);/* cout<<a<<" ";*/}}/*cout<<endl;*/linenum++;}start=vec_col[0][0];/* for(int icnt=0;icnt<vec_col.size();icnt++){cout<<vec_col[icnt]<<" ";}*/}string table::find_str(char row,char col){for(int x=0;x<vec_col.size();x++)for(int y=0;y<vec_row.size();y++){if(row==vec_col[x][0]&&col==vec_row[y][0]){return matrix[x+1][y+1];}}return"";}void an_process::analyse(table LL1_table,sentence input) {int icnt=0,jcnt=0,kcnt;string ac,prod="",re="";vector<char> stack;char Now_word=input.str_input[icnt];char NOW_state=LL1_table.start;string::const_iterator Eiter;string::const_iterator Biter;stack.push_back('#');stack.push_back(NOW_state);for(;icnt<input.str_input.size();){step.push_back(++jcnt);stack_note.push_back(stack);for(kcnt=icnt;kcnt<input.str_input.size();kcnt++){re=re+input.str_input[kcnt];}re=re+"#";remain.push_back(re);re.erase();Now_word=input.str_input[icnt];NOW_state=stack.back();if(NOW_state==Now_word){stack.erase(stack.end()-1);icnt++;production.push_back("(匹配)");}else{ac=LL1_table.find_str(NOW_state,Now_word);Biter=ac.begin();Biter--;Eiter=ac.end();Eiter--;if(ac=="ε"){prod=prod+NOW_state;prod=prod+"→";prod=prod+"ε";stack.erase(stack.end()-1);production.push_back(prod);prod.erase();}else if(ac!=""){stack.erase(stack.end()-1);prod.empty();prod=prod+NOW_state;prod=prod+"→"+ac;production.push_back(prod);prod.erase();for(;Eiter!=Biter;Eiter--){stack.push_back(*Eiter);}}else{cout<<"分析失败\n";exit(0);}}}if(stack.size()!=1||stack.back()!='#'){cout<<"分析失败\n";exit(0);}}void an_process::write_result(){step.push_back(step.back()+1);vector<char> a;a.push_back('#');stack_note.push_back(a);remain.push_back("#");production.push_back("接受");gotoxy(27,1);cout<<"输入串"<<'"'<<remain[0];cout<<"\b"<<'"'<<"的分析过程"<<endl<<endl;print2(step.size()+1,4);vector<int>::const_iterator iter1=step.begin();vector<vector<char> >::const_iterator iter2=stack_note.begin(); vector<string>::const_iterator iter3=remain.begin();vector<string>::const_iterator iter4=production.begin(); gotoxy(8,4);cout<<"步骤";gotoxy(27,4);cout<<"分析栈";gotoxy(44,4);cout<<"剩余输入串";gotoxy(63,4);cout<<"所用产生式";for(int xy=0;iter1!=step.end();iter1++){gotoxy(9,xy+6);cout<<(*iter1);xy=xy+2;}for(xy=0;iter2!=stack_note.end();iter2++) {gotoxy(27,xy+6);for(int icnt=0;icnt<(*iter2).size();icnt++) {cout<<(*iter2)[icnt];}xy=xy+2;}for(xy=0;iter3!=remain.end();iter3++){gotoxy(44,xy+6);cout<<(*iter3);xy=xy+2;}for(xy=0;iter4!=production.end();iter4++){gotoxy(63,xy+6);cout<<(*iter4);xy=xy+2;}cout<<endl<<endl;}void an_process::print2(int x,int y)//简易画线代码，呵呵,画行直线{int i,j;for(int icnt=0;icnt<y-1;icnt++){for(i=0;i<37/y;i++)printf("─");printf("┬");}for(i=0;i<37/y;i++)printf("─");putchar(10);for(icnt=0;icnt<y-1;icnt++) {for(i=0;i<37/y;i++)printf(" ");printf("│");}putchar(10);for(j=0;j<x-1;j++)//画5行直线{for(icnt=0;icnt<y-1;icnt++){for(i=0;i<37/y;i++)printf("─");printf("┼");}for(i=0;i<37/y;i++)printf("─");putchar(10);for(icnt=0;icnt<y-1;icnt++){for(i=0;i<37/y;i++)printf(" ");printf("│");}putchar(10);}for(icnt=0;icnt<y-1;icnt++) {for(i=0;i<37/y;i++)printf("─");printf("┴");}for(i=0;i<37/y;i++)printf("─");putchar(10);}void sentence::read_in(){cout<<"请输入需要分析的句子：\n";cin>>str_input;system("cls");}void main(){table LL1_table;sentence input;an_process A;input.read_in();LL1_table.read();A.analyse(LL1_table,input);A.write_result();}。
