专题3_LL(1)语法分析设计原理与实现

李若森 13281132 计科1301

一、 理论传授

语法分析的设计方法和实现原理；LL(1) 分析表的构造；LL(1)分析过程；LL(1)分析器的构造。

二、 目标任务

实验项目

实现LL(1)分析中控制程序（表驱动程序）；完成以下描述算术表达式的 LL(1)文法的LL(1)分析程序。

G[E]:

E→TE’

E’→ATE’|ε T→FT’

T’→MFT’|ε F→(E)|i A→+|- M→*|/

设计说明

终结符号i为用户定义的简单变量，即标识符的定义。加减乘除即运算符。

设计要求

(1) 输入串应是词法分析的输出二元式序列，即某算术表达式“专题 1”的输出结果，

输出为输入串是否为该文法定义的算术表达式的判断结果； (2) LL(1)分析程序应能发现输入串出错；

(3) 设计两个测试用例（尽可能完备，正确和出错），并给出测试结果。

任务分析

重点解决LL(1)表的构造和LL(1)分析器的实现。

三、 实现过程

实现LL(1)分析器

a) 将#号放在输入串S的尾部

b) S中字符顺序入栈 c) 反复执行c)，任何时候按栈顶Xm和输入ai依据分析表，执行下述三个动作之一。

构造LL(1)分析表

构造LL(1)分析表需要得到文法G[E]的FIRST集和FOLLOW集。

构造FIRST(α)

构造FOLLOW(A)

构造LL(1)分析表算法

根据上述算法可得G[E]的LL(1)分析表，如表3-1所示：

表3-1 LL(1)分析表

主要数据结构

pair:

用pair来存储单个二元组。该对照表由专题1定义。 map:

存储离散化后的终结符和非终结符。 vector[][]:

存储LL(1)分析表

函数定义

init:

void init();

功能：

初始化LL(1)分析表，关键字及识别码对照表，离散化（非）终结符 传入参数： （无） 传出参数： （无） 返回值： （无）