实验二编写语法分析程序

《实验二编写语法分析程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验二编写语法分析程序2.1实验类型设计型实验，6学时(2学时完成文法改造；2学时完成程序编码；2学时完成程序测试)2.2实验目的通过设计、编写、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握递归下降语法分析方法。2.3背景知识2.3.1递归下降分析自顶向下语法分析过程中，如果产生回溯，则分析过程需要穷举所有可能的推导，看是否能推导出待检查的单词序列，导致分析程序时间和空间开销增大，降低分析效率。而无回溯的自顶向下分析技术可根据输入串的当前单词，选择唯一的产生式构造推导过程，从而提高

2、分析效率。无回溯的自顶向下分析要求文法是LL(1)文法。递归下降分析程序的实现思想是：(1)分析程序由一组子程序组成，每个子程序对应于一个非终结符号。(2)每一个子程序的功能：选择正确的产生式右部，扫描相应的单词；产生式右部有非终结符号时，调用该非终结符号对应的子程序来完成。2.3.2LL(1)文法LL(1)文法满足以下三个条件：（1）文法不含左递归（2）文法的任何一个非终结符A的各个产生式的右部符号串的FIRST集两两不相交，即：若有A→α1

3、α2

4、…

5、αn，则FIRST(ai)∩FIRST(aj)=φ(i≠j，1≤i,j≤n

6、)（3）文法的任何一个非终结符A,若有A→α1

7、α2

8、…

9、αn且存在ai，有ε∈FIRST(αi)，则FIRST(αj)∩FOLLOW(A)=φ（i≠j，j=1,2,...,n）2.3.3文法改造1、消除直接左递归（将左递归改为右递归）：直接左递归形式：U→Ux

10、y；其中：x，y∈(VN∪VT)*，y不以U打头。直接左递归的消除：U→yU’U’→xU’

11、ε直接左递归的一般形式：U→Ux1

12、Ux2

13、…

14、Uxm

15、y1

16、y2

17、…

18、yn；其中：xi≠ε,yi都不以U打头。一般形式直接左递归的消除:U→y1U’

19、y2U’

20、…

21、ynU’U’

22、→x1U’

23、x2U’

24、…

25、xmU’

26、ε2、消除间接左递归：要求无环路（形如A⇒+A的推导）和无ε-产生式。（1）把非终结符按某一顺序排序为A1,A2…An。（2）for(i=1;i<=n;i++){for(j=1;j<=i-l;j++){if(Aj→δ1

27、δ2

28、…

29、δk,Ai→Ajγ)把Ai→Ajγ改写成Ai→δ1γ

30、δ2γ

31、…

32、δkγ;}消除关于Ai产生式的直接左递归;}（3）化简由（2）所得到的文法。（4）化简改写之后的文法，删除多余产生式。3、提取左公因子A→ab1

33、ab2……

34、abn

35、γ1……

36、γm改写成:A→aA’

37、γ

38、1……

39、γmA’→b1

40、b2……

41、bn2.3.4递归下降分析程序的基本架构定义：变量：ch，为当前符号；函数：READ(ch)：读输入串下一符号；对于每个非终结符号U→α1

42、α2

43、…

44、αn处理的方法如下：U（）{ifch∈FIRST(α1)thenP(α1)//处理α1的程序部分。elseifch∈FIRST(α2)thenP(α2)//处理α2的程序部分。…elseifch∈FIRST(αn)thenP(αn)elseifch∈FOLLOW(U)thenreturn//处理ε产生式情况。elseerror}对于每个右部α=x1

45、x2…xn的处理架构如下：P(α){P(x1);//处理x1的程序。P(x2);//处理x2的程序。………P(xn);//处理xn的程序。}对于右部中的每个符号xi；如果xi为终结符号：if(ch==a)READ(ch)elseerror如果xi为非终结符号，直接调用相应的过程：P(xi)。2.3.5编写递归下降分析程序一般步骤1)改写文法，消除二义性；2)消除左递归、提取左因子；3)求FIRST集、FOLLOW集；4)检查是不是LL(1)文法，若不是LL(1)，说明文法的复杂性超过自顶向下方法的分析能力（对文法的改造会影响文法

46、的可读性，可以采用超前读一个单词的来处理）。5)直接根据产生式设计相应的程序2.4实验内容1、语法规则TEST语言的语法规则如下：1)→{}2)→

47、ε3)→intID;4)→

48、ε5)→

49、at>

50、

51、

52、

53、

54、

55、6)→if()

56、if()<