基于Java实现一个简单的YACC

心已赠人 2024-04-01 15:16 110阅读 0赞

[资源下载地址][Link 1]：https://download.csdn.net/download/sheziqiong/86918785  
[资源下载地址][Link 1]：https://download.csdn.net/download/sheziqiong/86918785

## 实现一个简单的YACC ##

使用LL（1）分析法，按照cfg.txt中的语法对input.txt的输入流进行句法分析，并将结果打印在output.txt文件中。

### Content description ###

读入cfg.txt，分析产生式，并产生对应的LL(1)预测分析表PPT。

cfg具体样例参见.

输入文件input.txt包含待分析的字符流，样例如下：

i+i*i$

输出文件output.txt包含cfg，输入字符流，以及分析后的推导序列，样例如下：

CFG:
    S->TE
    E->+TE
    E->`
    T->FY
    Y->*FY
    Y->`
    F->i
    F->(S)
     
    Input stream of Characters:
    i+i*i$
     
    Output derivations:
    S->TE
    T->FY
    F->i
    Y->`
    E->+TE
    T->FY
    F->i
    Y->*FY
    F->i
    Y->`
    E->`
    success!

### Ideas/Methods ###

*  LL(1)分析法。
 *  对cfg.txt中的产生式逐个分析，通过first和follow函数构造PPT。
 *  建立分析栈，根据栈顶和读头下的字符查询PPT，操作栈，打印推导序列。

### Assumptions ###

Cfg.txt包含：

*  合法的，已消除左递归的，分开的上下文无关文法；
 *  所有出现的终结符和非终结符。
 *  以S为开始符，以$为结束符，以\`为空串，每段以空行分隔。

样例如下：

S->TE
    E->+TE
    E->`
    T->FY
    Y->*FY
    Y->`
    F->i
    F->(S)
    
    i,+,*,(,),$
    
    S,E,T,Y,F

### Description of important Data Structures ###

产生式：

public class Production {
    
       public Character left;
       public String right;

分别保存左部和右部。

预测分析表：

public class ParsingTable {
    
       private ArrayList<Production> productions = new ArrayList<Production>();
       ArrayList<Character> terminals = new ArrayList<Character>();
       ArrayList<Character> nonTerminals = new ArrayList<Character>();
       private int numOfTerminals;
       private int numOfNonTerminals;
       Production[][] table;

包含所有的产生式，终结符和非终结符，产生对应的预测分析表，由parser继承。

实现了first，follow函数，处理cfg的初始化。

文件IO：

实现了readfile，clearfile，writefile，getCFG函数，负责文件的输入输出和cfg的读入。

分析器：

public class Parser extends ParsingTable {
    
       //输入流
       private StringBuffer stringBuffer = new StringBuffer();

继承ParsingTable，负责句法分析。

### Description of core Algorithms ###

根据CFG构造PPT，根据PPT通过parser分析输入流。

### Use cases on running ###

参见的样例。

### Problems occurred and related solutions ###