Skip to content

Latest commit

 

History

History

LL1Parser

README.md

语法分析 - LL (1) 实验报告

2016/11/10

实验目的

  1. 编程实现对算术表达式的语法分析程序
  2. 理解并掌握语法分析程序

实验内容

实现如下文法的语法分析程序：

E -> E + T | E - T | T
T -> T * F | T / F | F
F -> ( E ) | num
  1. 实现自动构造LL(1)分析表
  2. 实现LL(1)分析程序

算法设计

Part 1

  • 读入文法
  • 消除左递归
    • 给定一个所有非终结符顺序，根据这个顺序遍历所有非终结符
      • 按顺序当前符号产生式中排在当前符号前边的非终结符用对应产生式代替
      • 所有带左递归产生式替换： A -> A alpha => A' -> alpha A'
      • 在所有产生式尾部插入 A'： A -> beta => A -> beta A'
      • 插入 A' -> epsilon
  • 提取左因子
    • 遍历所有非终结符的每个产生式找出公共前缀
    • 替换 A -> X alpha | X beta => _A -> alpha | beta
    • 如果alpha beta有空，插入 _A -> epsilon
    • 插入 A -> X _A
    • 循环这个过程直到无左因子
  • 构造LL(1)分析表
    • 找First集
      • Frist[终结符号] = { 终结符号 }
      • 遍历每个产生式每个符号
        • First[产生式左端非终结符] += First[当前符号]
        • 如果First[当前符号]没有epsilon
          • 结束遍历
        • 如果全部遍历的符号的First有epsilon
          • First[产生式左端非终结符] += { epsilon }
      • 循环这个过程直到不再增加
    • 找Follow集
      • 遍历每个产生式每个符号，跳过终止符号
        • 将下一个符号First集加入当前符号的Follow集
        • 如果下一个符号不存在 或 First[当前符号]有epsilon
          • Follow[当前符号] += Follow[产生式左端非终结符]
      • 循环这个过程直到不再增加
    • 生成分析表
      • 遍历First[每个产生式右端第一个符号]
        • 如果First[i]不为epsilon
          • 产生式 加入 分析表[产生式左端非终结符, First[i]]
        • 否则，遍历Follow[产生式左端非终结符]
          • 产生式 加入 分析表[产生式左端非终结符, Follow[i]]
      • 如果存在多重表项
        • 不是LL(1)文法，报错
    • 加入错误处理sync
      • 遍历Follow[每一个非终结符]
        • 如果 分析表[非终结符, Follow[i]]为空
          • sync 加入 分析表[非终结符, Follow[i]]
  • 打印文法
  • 打印LL(1)分析表

Part 2

  • 读入待分析表达式集
  • 分析表达式集
    • 切分表达式
    • 初始化分析器
      • 输入流尾部插入$
      • 分析栈压入 $ 和 起始符
    • 循环直到 栈空 或 输入读完
      • 如果栈顶是非终结符
        • 如果 分析表项 非空
          • 弹栈
          • 如果 分析表项 不为sync
            • 反向压入 分析表项，输出
          • 否则
            • 报错
        • 否则
          • 报错，后移指针
      • 如果栈顶是终止符号 或 $
        • 弹栈
        • 如果 栈顶 == 当前输入
          • 后移指针
          • 如果 栈顶 == 当前输入 == $
            • 退出循环
        • 否则
          • 报错
  • 输出分析结果

架构设计

LL1Parser

函数成员：

  • Parse (istream, ostream) // 分析待分析表达式集

Grammar

数据成员：

  • startSymbol
  • 集合: nonTerminalSymbols
  • 集合: terminalSymbols
  • 映射: productionRules
    • 非终结符 -> { 产生式 } = { { 符号 } }

函数成员：

  • FixLeftRecursion () // 消除左递归
  • FixLeftCommonFactor () // 提取左因子

LL1Grammar : Grammar

数据成员：

  • 继承 Grammar 成员
  • 映射: table
    • (终结符, 非终结符) -> 产生式 = { { 符号 } }

函数成员：

  • 继承 Grammar 成员
  • GetLL1Table () // 生成LL(1)分析表

Lexer

数据成员：

  • 集合: tokens

函数成员：

  • Lexer (istream, puncSet)
    • istream 待分析表达式输入流
    • puncSet 标点符号集合

输入输出

int main (int argc, char *argv[])

  • 检查argc 是否合法 (argc >= 3)
    • argv[1] 为语法定义文件
    • argv[2] 为待识别文件
  • 打开输入/输出文件，并判断释放成功
  • 将语法定义文件输入流传入LL1Parser，生成语法分析器
  • 将语法输出流用于打印语法及LL(1)分析表
  • 将待识别文件 输入/输出 流传入LL1Parser.Parse进行分析

输入格式

文件允许的换行符：

  • Windows \r\n
  • Linux \n

语法定义文件

每个非终止符号的所有推导用一行列出，各个产生式用管道线隔开， 各个符号之间用界符隔开：

E -> E + T | E - T | T
  • -> 表示推导运算
  • | 表示管道线
  • （空格）表示符号间的界符
  • num 表示数字
  • epsilon 表示空产生式
  • 其他符号 表示文法的符号
    • 在 -> 前出现的符号 为非终止符号
    • 所有符号除了非终止符号 为终止符号

待识别文件

行为单位的待分析表达式

输出格式

语法输出

  • 去左递归后的语法
    • 开始符号
    • 非终结符号
    • 终结符号
    • 产生式列表
  • LL(1)分析表

待识别文件输出

每一个待分析表达式的 最左推导/错误处理 结果

运行样例

Windows MSVC 2015 (Visual Studio 2015)

运行 LL1Parser.vcxproj, 并使用参数 Grammar.txt Input.txt

也可以编译为 LL1Parser.exe 之后

在命令提示符输入 LL1Parser Grammar.txt Input.txt

Remarks:

  • Grammar.txt 为文法输入
  • Input.txt 为表达式输入

Unix/Unix-like

在终端中输入

g++ LL1Parser.cpp -std=c++11 -o LL1Parser
./LL1Parser Grammar.txt Input.txt

Remarks:

  • Grammar.txt 为文法输入
  • Input.txt 为表达式输入

Input

Grammar.txt

E -> E + T | E - T | T
T -> T * F | T / F | F
F -> ( E ) | num

Input.txt

* (3.3 - 2) * + ( * + 2
(3.5/(2-4*.8/2)-2*3.+(2/(2)-2))+2

Output

Grammar.txt.output.txt

Grammar:
Starting Symbol:
	E
Non Terminal Symbols:
	E T F E' T' 
Terminal Symbols:
	( ) num + - * epsilon / 
Production Rules:
	E -> T E'
	T -> F T'
	F -> ( E ) | num
	E' -> + T E' | - T E' | epsilon
	T' -> * F T' | / F T' | epsilon

LL1 Table:
<E, (>         E -> T E'
<T, (>         T -> F T'
<F, (>         F -> ( E )
<F, $>         F -> sync
<T, $>         T -> sync
<E, $>         E -> sync
<T', $>        T' -> epsilon
<E, num>       E -> T E'
<T, num>       T -> F T'
<F, num>       F -> num
<E', $>        E' -> epsilon
<F, +>         F -> sync
<T, +>         T -> sync
<T', +>        T' -> epsilon
<E', +>        E' -> + T E'
<F, ->         F -> sync
<T, ->         T -> sync
<T', ->        T' -> epsilon
<E', ->        E' -> - T E'
<F, )>         F -> sync
<T, )>         T -> sync
<E, )>         E -> sync
<T', )>        T' -> epsilon
<E', )>        E' -> epsilon
<F, *>         F -> sync
<T', *>        T' -> * F T'
<F, />         F -> sync
<T', />        T' -> / F T'

Input.txt.output.txt

Parse $* (3.3 - 2) * + ( * + 2$ :
Err: E | *              Skip *
E -> T E'
T -> F T'
F -> ( E )
E -> T E'
T -> F T'
F -> num
T' -> epsilon
E' -> - T E'
T -> F T'
F -> num
T' -> epsilon
E' -> epsilon
T' -> * F T'
Err: F | +               Pop F
T' -> epsilon
E' -> + T E'
T -> F T'
F -> ( E )
Err: E | *              Skip *
Err: E | +              Skip +
E -> T E'
T -> F T'
F -> num
T' -> epsilon
E' -> epsilon
Err: ) | $               Pop )
T' -> epsilon
E' -> epsilon

Parse $(3.5/(2-4*.8/2)-2*3.+(2/(2)-2))+2$ :
E -> T E'
T -> F T'
F -> ( E )
E -> T E'
T -> F T'
F -> num
T' -> / F T'
F -> ( E )
E -> T E'
T -> F T'
F -> num
T' -> epsilon
E' -> - T E'
T -> F T'
F -> num
T' -> * F T'
F -> num
T' -> / F T'
F -> num
T' -> epsilon
E' -> epsilon
T' -> epsilon
E' -> - T E'
T -> F T'
F -> num
T' -> * F T'
F -> num
T' -> epsilon
E' -> + T E'
T -> F T'
F -> ( E )
E -> T E'
T -> F T'
F -> num
T' -> / F T'
F -> ( E )
E -> T E'
T -> F T'
F -> num
T' -> epsilon
E' -> epsilon
T' -> epsilon
E' -> - T E'
T -> F T'
F -> num
T' -> epsilon
E' -> epsilon
T' -> epsilon
E' -> epsilon
T' -> epsilon
E' -> + T E'
T -> F T'
F -> num
T' -> epsilon
E' -> epsilon