基于Go实现语法分析程序【100012601】

# 大作业 - 语法分析程序 ## 实验内容及要求 编写语法分析程序，实现对算术表达式的语法分析。要求所分析算数表达式由如下的文法产生。 ``` E→ E+T | E–T | T T→ T*F | T/F | F F→ (E) | num ``` ## 实验要求 在对输入的算术表达式进行分析的过程中，依次输出所采用的产生式。 ### 实现方法要求： #### ~~方法 1：~~ ~~编写递归调用程序实现自顶向下的分析。~~ #### 方法 2： 编写 LL(1)语法分析程序，要求如下。 （必做） 1. 编程实现算法 4.2，为给定文法自动构造预测分析表。 2. 编程实现算法 4.1，构造 LL(1)预测分析程序 。 #### 方法 3： 编写语法分析程序实现自底向上的分析，要求如下。（必做） 1. 构造识别该文法所有活前缀的 DFA。 2. 构造该文法的 LR 分析表。 3. 编程实现算法 4.3，构造 LR 分析程序。 #### ~~方法 4：~~ ~~利用 YACC 自动生成语法分析程序，调用 LEX 自动生成的词法分析程序。~~ --- # 程序使用说明 ## 入口 程序的入口文件为 `gram/main/main.go` - 直接运行程序：`go run main.go` - 构建可执行程序：`go build main.go` 注意：请在 `terminal` 中运行程序，直接点击程序可能会闪一下然后消失 ## 直接运行可执行文件 直接运行： - `gram/main(win).exe` （windows） - `gram/main(mac)` （macos） ## 程序输入 程序的所有输入是以 JSON 文件的形式输入的，文件放在 `gram/base/def.json`，其示例结构如下： ```json { "tags": [ { "type": "终结符", "value": "+" }, { "type": "终结符", "value": "-" }, { "type": "终结符", "value": "*" }, { "type": "终结符", "value": "/" }, { "type": "终结符", "value": "(" }, { "type": "终结符", "value": ")" }, { "type": "终结符", "value": "num" }, { "type": "终结符", "value": "ε" }, { "type": "非终结符", "value": "E" }, { "type": "非终结符", "value": "F" }, { "type": "非终结符", "value": "T" } ], "productions": [ "E → E+T | E-T | T", "T → T*F | T/F | F", "F → (E) | num" ], "input": "(num/num)", "method": "LR" } ``` JSON 文件中应包含：`tags`, `productions`, `input` 和 `method` ### `tags` type 只能为 `"终结符"` 和 `"非终结符"` 两者之一 value 为终结符或非终结符的值 ### `productions` 生成式，是一个字符串数组，子式与子式之间用 `|` 分割，左部与右部之间用 `→` 分割，允许存在空格，分析程序在执行分析之前会先去除空格 ### `input` 待分析的输入串，是一个字符串，注意：不需要在这里手动添加 `$` ### `method` 分析程序使用的方法，只能为 `LR` 和 `LL` 二者之一 --- # 程序设计说明 > 姓名：陈威豪 > 学号：2019211232 > 班级：2019211303 ## 手工计算例题 ### 原表达式 ```txt E → E+T | E–T | T T → T*F | T/F | F F → (E) | num ``` ### 消除左递归 ```txt E → TE' E' → +TE' | -TE' | ε T → FT' T' → *FT' | /FT' | ε F → (E) | num ``` ### 原表达式 `FIRST` 集 ```txt E: ( num F: ( num T: ( num ``` ### 原表达式 `FOLLOW` 集 ```txt E: $ + - ) F: $ ) + - * / T: $ ) + - * / ``` ### 消除左递归 `FIRST` 集 ```txt E: ( num F: ( num T: ( num E': + - ε T': * / ε ``` ### 消除左递归 `FOLLOW` 集 ```txt E: $ ) F: * / + - $ ) T: + - $ ) E': $ ) T': + - $ ) ``` ### 求 LL 分析表 ```txt +----+----------+----------+----------+----------+--------+-------+--------+-------+ | | + | - | * | / | ( | ) | num | $ | +----+----------+----------+----------+----------+--------+-------+--------+-------+ | E' | E'->+TE' | E'->-TE' | | | | E'->ε | | E'->ε | | E | | | | | E->TE' | | E->TE' | | | F | | | | | F->(E) | | F->num | | | T' | T'->ε | T'->ε | T'->*FT' | T'->/FT' | | T'->ε | | T'->ε | | T | | | | | T->FT' | | T->FT' | | +----+----------+----------+----------+----------+--------+-------+--------+-------+ ``` ### LL 分析过程 ```txt +------+-------------+------------+----------+ | STEP | STACK | INPUT | OUTPUT | +------+-------------+------------+----------+ | (1) | $E | (num/num)$ | E->TE' | | (2) | $E'T | (num/num)$ | T->FT' | | (3) | $E'T'F | (num/num)$ | F->(E) | | (5) | $E'T')E | num/num)$ | E->TE' | | (6) | $E'T')E'T | num/num)$ | T->FT' | | (7) | $E'T')E'T'F | num/num)$ | F->num | | (9) | $E'T')E'T' | /num)$ | T'->/FT' | | (11) | $E'T')E'T'F | num)$ | F->num | | (13) | $E'T')E'T' | )$ | T'->ε | | (14) | $E'T')E' | )$ | E'->ε | +------+-------------+------------+----------+ ``` ### LR1 的项目集规范族 ```txt I0: E'->·E, $ E->·E+T, $ + - E->·E-T, $ + - E->·T, $ + - T->·T*F, $ + - * / T->·T/F, $ + - * / T->·F, $ + - * / F->·(E), $ + - * / F->·num, $ + - * / I1: E'->E·, $ E->E·+T, $ + - E->E·-T, $ + - I2: E->T·, $ + - T->T·*F, $ + - * / T->T·/F, $ + - * / I3: T->F·, $ + - * / I4: F->(·E), $ + - * / E->·E+T, ) + - E->·E-T, ) + - E->·T, ) + - T->·T*F, ) + - * / T->·T/F, ) + - * / T->·F, ) + - * / F->·(E), ) + - * / F->·num, ) + - * / I5: F->num·, $ + - * / I6: E->E+·T, $ + - T->·T*F, $ + - * / T->·T/F, $ + - * / T->·F, $ + - * / F->·(E), $ + - * / F->·num, $ + - * / I7: E->E-·T, $ + - T->·T*F, $ + - * / T->·T/F, $ + - * / T->·F, $ + - * / F->·(E), $ + - * / F->·num, $ + - * / I8: T->T*·F, $ + - * / F->·(E), $ + - * / F->·num, $ + - * / I9: T->T/·F, $ + - * / F->·(E), $ + - * / F->·num, $ + - * / I10: F->(E·), $ + - * / E->E·+T, ) + - E->E·-T, ) + - I11: E->T·, ) + - T->T·*F, ) + - * / T->T·/F, ) + - * / I12: T->F·, ) + - * / I13: F->(·E), ) + - * / E->·E+T, ) + - E->·E-T, ) + - E->·T, ) + - T->·T*F, ) + - * / T->·T/F, ) + - * / T->·F, ) + - * / F->·(E), ) + - * / F->·num, ) + - * / I14: F->num·, ) + - * / I15: E->E+T·, $ + - T->T·*F, $ + - * / T->T·/F, $ + - * / I16: E->E-T·, $ + - T->T·*F, $ + - * / T->T·/F, $ + - * / I17: T->T*F·, $ + - * / I18: T->T/F·, $ + - * / I19: F->(E)·, $ + - * / I20: E->E+·T, ) + - T->·T*F, ) + - * / T->·T/F, ) + - * / T->·F, ) + - * / F->·(E), ) + - * / F->·num, ) + - * / I21: E->E-·T, ) + - T->·T*F, ) + - * / T->·T/F, ) + - * / T->·F, ) + - * / F->·(E), ) + - * / F->·num, ) + - * / I22: T->T*·F, ) + - * / F->·(E), ) + - * / F->·num, ) + - * / I23: T->T/·F, ) + - * / F->·(E), ) + - * / F->·num, ) + - * / I24: F->(E·), ) + - * / E->E·+T, ) + - E->E·-T, ) + - I26: E->E+T·, ) + - T->T·*F, ) + - * / T->T·/F, ) + - * / I27: E->E-T·, ) + - T->T·*F, ) + - * / T->T·/F, ) + - * / I28: T->T*F·, ) + - * / I29: T->T/F·, ) + - * / ``` ### LR 分析表 ```txt +----+-----+-----+-----+-----+-----+-----+-----+-----+----+----+----+ | | + | - | * | / | ( | ) | num | $ | E | F | T | +----+-----+-----+-----+-----+-----+-----+-----+-----+----+----+----+ | 0 | | | | | S4 | | S5 | | 1 | 3 | 2 | | 1 | S6 | S7 | | | | | | ACC | | | | | 2 | R3 | R3 | S8 | S9 | | R3 | | R3 | | | | | 3 | R6 | R6 | R6 | R6 | | R6 | | R6 | | | | | 4 | | | | | S13 | | S14 | | 10 | 12 | 11 | | 5 | R8 | R8 | R8 | R8 | | R8 | | R8 | | | | | 6 | | | | | S4 | | S5 | | | 3 | 15 | | 7 | | | | | S4 | | S5 | | | 3 | 16 | | 8 | | | | | S4 | | S5 | | | 17