编译原理之最左推导和最右推导

时间:2022-01-16 19:35:27

符号串的最左推导及最右推导

 

需求分析

 

1)输入一个文法,可以有多个非终结符号,每个非终结符号可有多条规则。

 

2)输入要分析的符号串

 

3)分别采用最左推导和最右推导进行符号串的分析,请输出推导过程。

 

文法为:

E->CB

C->c

B->b

 

假如有个要分析的字符串为EB

最左推导的分析为

1         CBB

2         cBB

3         cbB

4         cbb

最右推导的分析为

1         Eb

2         CBb

3         cBb

4         cbb

 

 

1 输入文法

2 输入要分析的字符串

3 选择适当的文法

4 判断是否要分析的字符串已经分析完

N

5  输出分析结果并结束

1 输入文法

2 输入要分析的字符串

3 选择适当的文法

4 判断是否要分析的字符串已经分析完

N

5  输出分析结果并结束

Y

详细设计

1.界面设计

利用VC++的MFC的单对话框做模板,输入文法和要分析的字符串分别用一个Text来输入,输出的最左推导和最右推导结果在ListBox,一个按钮来确认

 

2.模块算法(伪代码)

(1)   最左推导

while(这不是最后一个字符)

{
if(
这是一个非终结符号)

   文法分析字符串

把字符串放进链表头

   输出当前分析的字符串

else

   指向后一个字符

}

(2)   最右推导

while(这不是最后一个字符)

{
if(
这是一个非终结符号)

   文法分析字符串

把字符串放进链表尾

   输出当前分析的字符串

else

   指向前一个字符

}

 

3)何为非终结符号

      E->CD

      可以看出凡是在箭头左边的为非终结符号

4)分析文法表

     例如E->C

         C->c

      由此可见:

->左边的为非终结符号,->右边的为要分析的文法