基于Java实现的语法分析器

太过爱你忘了你带给我的痛 2024-04-06 10:44 63阅读 0赞

## 语法分析器的简单实现 ##

## 一、实验目的 ##

通过构建一个简单的语法分析程序，进一步熟悉语法分析的过程以及加深对 First 和Follow 的认识。

## 二、实验描述 ##

本次实验使用 Java 语言编写，简单实现了对 C 语言程序的语法分析。程序的输入是 C 语言程序代码 program.c 文件以及已经定义好的文法 CFG.txt 文件。程序的输出是控制台和 output.txt 文件，内容是语法分析的过程。本实验中用到的词法分析部分是实验一的词法分析器。

## 三、实验方法 ##

本次实验选用的方法是 PPT 中给出的第一种方法中的 a 方法，根据文法编程构建 LL(1) 预测分析表来进行语法分析。

实验设想

无。

相关的自动机描述

大部分同词法分析。

## 四、数据结构的定义 ##

Lex 类：词法分析程序

Token 类：Token 序列中的元素

Production 类：产生式类，包括两个属性，一个是 left（String 类型），表示产生式的左部；另一个是 right（List类型），表示产生式的右部。  
FirstFollow 类：表示 First 或 Follow 的类，包括两个属性，一个是 left（String 类型），另一个是 right（List类型）。  
Syntax 类：语法分析程序核心 终结符和非终结符分别用 List类型来表示。

产生式用 List类型来表示。

符号的 First 和 Follow 分别用 List类型来表示。

预测分析表用 Production\[\]\[\]类型表示，还需要借助终结符和非终结符的 List作为表头。

语法分析过程中的栈用 Java 自带的 Stack来表示。

Token 序列（简化版）用 List类型来表示。

## 五、核心算法描述 ##

程序的核心算法主要有四个：

getFirst()：获得符号的 First 集合，算法在龙书的 P140.

getFollow()：获得符号的 Follow 集合，算法在龙书的 P140-141.

getParsingTable()：构建预测分析表，算法在龙书的 P142-143，算法 4.31

syntaxParsing()：表驱动的预测语法分析，算法在龙书的 P144，算法 4.34

### 语法分析的过程输出 output.txt： ###

Match:  	 
    Stack: 	 	$ Function  
    Input: 	 	int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else 
    { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $  
    Action:  	输出: Program -> Function  
    Match:  	 
    Stack: 	 	$ } Return Statement { ) Para ( FuncName DataType  
    Input: 	 	int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else 
    { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $  
    Action:  	输出: Function -> DataType FuncName ( Para ) { Statement Return }  
    Match:  	 
    Stack: 	 	$ } Return Statement { ) Para ( FuncName int  
    Input: 	 	int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else 
    { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $  
    Action:  	输出: DataType -> int  
    Match:  	int  
    Stack: 	 	$ } Return Statement { ) Para ( FuncName  
    Input: 	 	ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int 
    ID = NUM ; ID = ID + NUM ; } } return NUM ; } $

Action: 匹配 int

Match:  	int  
    Stack: 	 	$ } Return Statement { ) Para ( ID  
    Input: 	 	ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int 
    ID = NUM ; ID = ID + NUM ; } } return NUM ; } $  
    Action:  	输出: FuncName -> ID  
    Match:  	int ID  
    Stack: 	 	$ } Return Statement { ) Para (  
    Input: 	 	( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID 
    = NUM ; ID = ID + NUM ; } } return NUM ; } $

Action: 匹配 ID

Match: 	int ID (  
    Stack: 	 	$ } Return Statement { ) Para  
    Input: 	 	float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = 
    NUM ; ID = ID + NUM ; } } return NUM ; } $

Action: 匹配 (

Match:  	int ID (  
    Stack: 	 	$ } Return Statement { ) ID DataType  
    Input: 	 	float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = 
    NUM ; ID = ID + NUM ; } } return NUM ; } $  
    Action:  	输出: Para -> DataType ID  
    Match:  	int ID (  
    Stack: 	 	$ } Return Statement { ) ID float  
    Input: 	 	float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = 
    NUM ; ID = ID + NUM ; } } return NUM ; } $  
    Action:  	输出: DataType -> float  
    Match:  	int ID ( float  
    Stack: 	 	$ } Return Statement { ) ID  
    Input: 	 	ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; 
    ID = ID + NUM ; } } return NUM ; } $

Action: 匹配 float

Match:  	int ID ( float ID  
    Stack: 	 	$ } Return Statement { )  
    Input: 	 	) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; 
    ID = ID + NUM ; } } return NUM ; } $

Action: 匹配 ID

Match:  	int ID ( float ID )  
    Stack: 	 	$ } Return Statement {  
    Input: 	 	{ while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID 
    = ID + NUM ; } } return NUM ; } $

Action: 匹配 )

Match:  	int ID ( float ID ) {  
    Stack: 	 	$ } Return Statement  
    Input: 	 	while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID 
    = ID + NUM ; } } return NUM ; } $

Action: 匹配 \{

Match:  	int ID ( float ID ) {  
    Stack: 	 	$ } Return Statement S  
    Input: 	while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID 
    = ID + NUM ; } } return NUM ; } $  
    Action:  	输出: Statement -> S Statement  
    Match:  	int ID ( float ID ) {  
    Stack: 	 	$ } Return Statement B ) C ( while  
    Input: 	 	while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID 
    = ID + NUM ; } } return NUM ; } $  
    Action:  	输出: S -> while ( C ) B  
    Match:  	int ID ( float ID ) { while  
    Stack: 	 	$ } Return Statement B ) C (  
    Input: 	 	( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + 
    NUM ; } } return NUM ; } $

Action: 匹配 while

Match:  	int ID ( float ID ) { while (  
    Stack: 	 	$ } Return Statement B ) C  
    Input: 	 	ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + 
    NUM ; } } return NUM ; } $

Action: 匹配 (

Match:  	int ID ( float ID ) { while (  
    Stack: 	 	$ } Return Statement B ) Keyword CompareOP Keyword  
    Input: 	 	ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + 
    NUM ; } } return NUM ; } $  
    Action:  	输出: C -> Keyword CompareOP Keyword  
    Match:  	int ID ( float ID ) { while (  
    Stack: 	 	$ } Return Statement B ) Keyword CompareOP ID  
    Input: 	 	ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + 
    NUM ; } } return NUM ; } $  
    Action:  	输出: Keyword -> ID  
    Match:  	int ID ( float ID ) { while ( ID  
    Stack: 	 	$ } Return Statement B ) Keyword CompareOP  
    Input: 	 	<= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + 
    NUM ; } } return NUM ; } $

Action: 匹配 ID

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement B ) Keyword &lt;=</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>&lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID +</td> 
  </tr> 
 </tbody> 
</table>

NUM ; } } return NUM ; } $  
    Action: 	输出: CompareOP -> <=  
    Match:  	int ID ( float ID ) { while ( ID <=  
    Stack: 	 	$ } Return Statement B ) Keyword  
    Input:  NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $

Action: 匹配 <=

Match:  	int ID ( float ID ) { while ( ID <=  
    Stack: 	 	$ } Return Statement B ) NUM  
    Input:  NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $  
    Action:  	输出: Keyword -> NUM  
    Match:  	int ID ( float ID ) { while ( ID <= NUM  
    Stack: 	 	$ } Return Statement B )  
    Input:  ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $

Action: 匹配 NUM

Match:  	int ID ( float ID ) { while ( ID <= NUM )  
    Stack: 	 	$ } Return Statement B  
    Input:  { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $

Action: 匹配 )

Match:  	int ID ( float ID ) { while ( ID <= NUM )  
    Stack: 	 	$ } Return Statement } Statement {  
    Input:  { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $  
    Action:  	输出: B -> { Statement }  
    Match:  	int ID ( float ID ) { while ( ID <= NUM ) {  
    Stack: 	 	$ } Return Statement } Statement  
    Input: 	 	if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $

Action: 匹配 \{

Match:  	int ID ( float ID ) { while ( ID <= NUM ) {

<table> 
 <thead> 
  <tr> 
   <th>Stack:</th> 
   <th>$ } Return Statement } Statement S</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Input: ；NUM ; } $</td> 
   <td>if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td>输出: Statement -&gt; S Statement</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <th>Match:</th> 
   <th>int ID ( float ID ) { while ( ID &lt;= NUM ) { </th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement D B ) C ( if</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return</td> 
  </tr> 
  <tr> 
   <td>NUM ; } $ Action: ；</td> 
   <td>输出: S -&gt; if ( C ) B D</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement D B ) C (</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return</td> 
  </tr> 
  <tr> 
   <td>NUM ; } $ Action: ；</td> 
   <td>匹配 if</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if (</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement D B ) C</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return</td> 
  </tr> 
  <tr> 
   <td>NUM ; } $ Action: ；</td> 
   <td>匹配 (</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if (</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement D B ) Keyword CompareOP Keyword</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return</td> 
  </tr> 
  <tr> 
   <td>NUM ; } $ Action: ；</td> 
   <td>输出: C -&gt; Keyword CompareOP Keyword</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if (</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement D B ) Keyword CompareOP ID</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return</td> 
  </tr> 
  <tr> 
   <td>NUM ; } $ Action: ；</td> 
   <td>输出: Keyword -&gt; ID</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement D B ) Keyword CompareOP</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>== NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; }</td> 
  </tr> 
  <tr> 
   <td>$ ；Action: ；</td> 
   <td>匹配 ID</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement D B ) Keyword ==</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>== NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; }</td> 
  </tr> 
  <tr> 
   <td>$ ；Action: ；</td> 
   <td>输出: CompareOP -&gt; ==</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID ==</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement D B ) Keyword</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <th>Input:</th> 
   <th></th> 
   <th>NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; }</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>$ Action: ；</td> 
   <td></td> 
   <td>匹配 ==</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID ==</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D B ) NUM</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; }</td> 
  </tr> 
  <tr> 
   <td>$ ；Action:</td> 
   <td></td> 
   <td>输出: Keyword -&gt; NUM</td> 
  </tr> 
  <tr> 
   <td>；Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D B )</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td></td> 
   <td>匹配 NUM</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM )</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D B</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>{ ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td></td> 
   <td>匹配 )</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM )</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D } Statement { </td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>{ ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td></td> 
   <td>输出: B -&gt; { Statement }</td> 
  </tr> 
  <tr> 
   <td>；Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { </td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D } Statement</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td></td> 
   <td>匹配 { </td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { </td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D } Statement S</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td></td> 
   <td>输出: Statement -&gt; S Statement</td> 
  </tr> 
  <tr> 
   <td>；Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { </td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D } Statement N Keyword = ID</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td></td> 
   <td>输出: S -&gt; ID = Keyword N</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D } Statement N Keyword =</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>= NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td></td> 
   <td>匹配 ID</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <th>；Match:</th> 
   <th></th> 
   <th>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID =</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D } Statement N Keyword</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td></td> 
   <td>匹配 =</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID =</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D } Statement N NUM</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td></td> 
   <td>输出: Keyword -&gt; NUM</td> 
  </tr> 
  <tr> 
   <td>；Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D } Statement N</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td></td> 
   <td>匹配 NUM</td> 
  </tr> 
  <tr> 
   <td>；Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D } Statement ;</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td></td> 
   <td>输出: N -&gt; ;</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ;</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D } Statement</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>} else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td></td> 
   <td>匹配 ;</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ;</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D }</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>} else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td></td> 
   <td>输出: Statement -&gt; ε</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; }</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement D</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td></td> 
   <td>匹配 }</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; }</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement B else</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td></td> 
   <td>输出: D -&gt; else B</td> 
  </tr> 
  <tr> 
   <td>；Match:</td> 
   <td></td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; } else</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td></td> 
   <td>$ } Return Statement } Statement B</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td></td> 
   <td>{ int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <th>Action: ；</th> 
   <th>匹配 else</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; } else</td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement } Statement { </td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>{ int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td>输出: B -&gt; { Statement }</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { </td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement } Statement</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td>匹配 { </td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { </td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement } Statement S</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td>输出: Statement -&gt; S Statement</td> 
  </tr> 
  <tr> 
   <td>；Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { </td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement } Statement M ID DataType</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td>输出: S -&gt; DataType ID M</td> 
  </tr> 
  <tr> 
   <td>；Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { </td> 
  </tr> 
  <tr> 
   <td>Stack:</td> 
   <td>$ } Return Statement } Statement } Statement M ID int</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action: ；</td> 
   <td>输出: DataType -&gt; int</td> 
  </tr> 
  <tr> 
   <td>Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; } else</td> 
  </tr> 
  <tr> 
   <td>{ int ； Stack:</td> 
   <td>$ } Return Statement } Statement } Statement M ID</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>ID = NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td>匹配 int</td> 
  </tr> 
  <tr> 
   <td>；Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; } else</td> 
  </tr> 
  <tr> 
   <td>{ int ID ； Stack:</td> 
   <td>$ } Return Statement } Statement } Statement M</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>= NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td>匹配 ID</td> 
  </tr> 
  <tr> 
   <td>；Match:</td> 
   <td>int ID ( float ID ) { while ( ID &lt;= NUM ) { if ( ID == NUM ) { ID = NUM ; } else</td> 
  </tr> 
  <tr> 
   <td>{ int ID ； Stack:</td> 
   <td>$ } Return Statement } Statement } Statement ; NUM =</td> 
  </tr> 
  <tr> 
   <td>Input:</td> 
   <td>= NUM ; ID = ID + NUM ; } } return NUM ; } $</td> 
  </tr> 
  <tr> 
   <td>Action:</td> 
   <td>输出: M -&gt; = NUM ;</td> 
  </tr> 
 </tbody> 
</table>

Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID =  
    	Stack: 	 	$ } Return Statement } Statement } Statement ; NUM  
    	Input: 	 	NUM ; ID = ID + NUM ; } } return NUM ; } $  
    	Action:  	匹配 = 
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM  
    	Stack: 	 	$ } Return Statement } Statement } Statement ;  
    	Input: 	 	; ID = ID + NUM ; } } return NUM ; } $  
    	Action:  	匹配 NUM 
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ;  
    	Stack: 	 	$ } Return Statement } Statement } Statement  
    	Input: 	 	ID = ID + NUM ; } } return NUM ; } $  
    	Action:  	匹配 ; 
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ;  
    	Stack: 	 	$ } Return Statement } Statement } Statement S  
    	Input: 	 	ID = ID + NUM ; } } return NUM ; } $  
    	Action:  	输出: Statement -> S Statement  
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ;  
    	Stack: 	 	$ } Return Statement } Statement } Statement N Keyword = ID  
    	Input: 	 	ID = ID + NUM ; } } return NUM ; } $  
    	Action:  	输出: S -> ID = Keyword N  
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID  
    	Stack: 	 	$ } Return Statement } Statement } Statement N Keyword =  
    	Input: 	 	= ID + NUM ; } } return NUM ; } $  
    	Action:  	匹配 ID 
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID =  
    	Stack: 	 	$ } Return Statement } Statement } Statement N Keyword  
    	Input: 	 	ID + NUM ; } } return NUM ; } $  
    	Action:  	匹配 = 
     
    	Match:  	int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else

{ int ID = NUM ; ID =  
    	Stack: 	 	$ } Return Statement } Statement } Statement N ID  
    	Input: 	 	ID + NUM ; } } return NUM ; } $  
    	Action:  	输出: Keyword -> ID  
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID  
    	Stack: 	 	$ } Return Statement } Statement } Statement N  
    	Input: 	 	+ NUM ; } } return NUM ; } $  
    	Action:  	匹配 ID 
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID  
    	Stack: 	 	$ } Return Statement } Statement } Statement ; Keyword OP  
    	Input: 	 	+ NUM ; } } return NUM ; } $  
    	Action:  	输出: N -> OP Keyword ;  
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID  
    	Stack: 	 	$ } Return Statement } Statement } Statement ; Keyword +  
    	Input: 	 	+ NUM ; } } return NUM ; } $  
    	Action:  	输出: OP -> +  
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID +  
    	Stack: 	 	$ } Return Statement } Statement } Statement ; Keyword  
    	Input: 	 	NUM ; } } return NUM ; } $  
    	Action:  	匹配 + 
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID +  
    	Stack: 	 	$ } Return Statement } Statement } Statement ; NUM  
    	Input: 	 	NUM ; } } return NUM ; } $  
    	Action:  	输出: Keyword -> NUM  
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM  
    	Stack: 	 	$ } Return Statement } Statement } Statement ;  
    	Input: 	 	; } } return NUM ; } $  
    	Action:  	匹配 NUM 
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ;  
    	Stack: 	 	$ } Return Statement } Statement } Statement

Input: 	 	} } return NUM ; } $  
    	Action:  	匹配 ; 
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ;  
    	Stack: 	 	$ } Return Statement } Statement }  
    	Input: 	 	} } return NUM ; } $  
    	Action:  	输出: Statement -> ε  
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; }  
    	Stack: 	 	$ } Return Statement } Statement  
    	Input: 	 	} return NUM ; } $  
    	Action:  	匹配 } 
     
    	Match:  	int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else 
    { int ID = NUM ; ID = ID + NUM ; }  
    	Stack: 	 	$ } Return Statement }  
    	Input: 	 	} return NUM ; } $  
    	Action:  	输出: Statement -> ε  
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } }  
    	Stack: 	 	$ } Return Statement  
    	Input: 	 	return NUM ; } $  
    	Action:  	匹配 } 
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } }  
    	Stack: 	 	$ } Return  
    	Input: 	 	return NUM ; } $  
    	Action:  	输出: Statement -> ε  
     
    	Match:  	int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else 
    { int ID = NUM ; ID = ID + NUM ; } }  
    	Stack: 	 	$ } ; Keyword return  
    	Input: 	 	return NUM ; } $  
    	Action:  	输出: Return -> return Keyword ;  
     
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return  
    	Stack: 	 	$ } ; Keyword  
    	Input: 	 	NUM ; } $  
    	Action:  	匹配 return

Match:  	int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else 
    { int ID = NUM ; ID = ID + NUM ; } } return  
    Stack: 	 	$ } ; NUM  
    Input: 	 	NUM ; } $  
    Action:  	输出: Keyword -> NUM  
    Match:  	int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else 
    { int ID = NUM ; ID = ID + NUM ; } } return NUM  
    Stack: 	 	$ } ;  
    Input: 	 	; } $

Action: 匹配 NUM

Match:  	int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else 
    { int ID = NUM ; ID = ID + NUM ; } } return NUM ;  
    Stack: 	 	$ }  
    Input: 	 	} $  
    Action:  	匹配 ; 
    Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; }  
    Stack: 	 	$  
    Input: 	 	$

Action: 匹配 \}

Match:  int ID ( float ID ) { while ( ID <= NUM ) { if ( ID == NUM ) { ID = NUM ; } else { int ID = NUM ; ID = ID + NUM ; } } return NUM ; } $  
    Stack: 	 	 
    Input:

Action: 匹配 $