基于C++实现的算符优先文法分析

TrueLove

发布日期: 2021-04-13 08:37:17 浏览量: 189
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

一、实验内容与要求

  • 根据算符优先分析算法,编写一个语法分析程序,可以选择以下三项之一作为分析算法中的输入:

    • 直接输入根据已知文法人工构造的算符优先关系矩阵
    • 输入已知文法和 FIRST、LAST 集合,由程序自动生成该文法的算法优先关系矩阵
    • 输入已知文法,由程序自动生成该文法的算法优先关系矩阵
  • 程序具有通用性,即所编制的语法分析程序能够适用于不同文法以及各种输入单词串,并能够判断该文法是否为算符文法和算符优先文法

  • 对输入的一个文法和一个单词串,程序能正确判断此单词是否为该文法的句子,并要求输出分析过程和语法树

二、实验内容选择

  • 选择第三项要求:

    • 输入已知文法,由程序自动生成该文法的算法优先关系矩阵
  • 程序具有通用性,即所编制的语法分析程序能够适用于不同文法以及各种输入单词串,并能够判断该文法是否为算符文法和算符优先文法

  • 对输入的一个文法和一个单词串,程序能正确判断此单词是否为该文法的句子,并要求输出分析过程和语法树

三、实验环境

  • 开发语言:C++

  • 开发环境:Mac OSX 平台下的 g++ 编译器

  • 版本:Apple LLVM 9.0.0

由于生成的可执行文件为 Unix 可执行文件,故在 Windows 环境下无法运行。

四、算符优先分析法

4.1 算符优先文法

定义:设有不含空串的一文法 G,如果 G 中没有形如 G>……BC……的产生式,其中 B 和 C 为非终结符,且对任意两个终结符 a,b 之间之多只有<,>,=,三种关系的一种成立,则称 G 是一个算符优先文法。

非终结符的 FIRSTVT 集合和 LASTVT 集合:

  • FIRSTVT(B) = {b|B→b…或 B→Cb…}

  • LASTVT(B) = {b|B→…a 或 B→…aC}

4.2 算符优先矩阵

算符优先关系矩阵,判断输入是否满足已知文法的依据。根据非终结符的FIRSTVT 集合和 LASTVT 集合产生。

  • “=”关系:若 A→…ab…或 A→…aBb…,则 a=b;

  • “<·”关系:若 A→…aB…,对每一个 b 属于 FIRSTVT(B),有 a <· b;

  • “·>”关系:若 A→…Bb…,对每一个 a 属于 LASTVT(B),有 a ·> b。

4.3 如何规约

在分析过程中,利用分析栈存放已识别的那部分句型,而句型的其余部分由剩余输入串组成,通过比较栈顶符号和下一个输入符号之间的关系,可以判别栈顶符号是否为句柄尾符号。如果是句柄尾,则沿栈顶向下,在栈内寻找句柄头。由之间包括的符号串就是句柄,然后把它们弹出栈,并代之以归约后的非终结符。这样就完成了一次归约过程。

4.4 算符优先分析方法的局限性

由于算符优先分析法去掉了单非终结符之间的归约,尽管在分析过程中,当决定是否为句柄时采取一些检查措施,但仍难完全避免把错误的句子得到正确的归约。

此外,通常一个适用语言的文法也很难满足算符优先文法的条件,因而致使算符优先分析法仅适用于表达式的语法分析。

五、概要设计

算符优先文法的执行过程为:输入已知文法,分析其正确性,提取非终结符和终结符,构造非终结符的 FIRSTVT 集和 LASTVT 集,再次基础上构造算符优先关系矩阵,并用来判断表达式是否符合该文法。

算符优先文法程序总的流程图为:

5.1 文法每个非终结符的 FIRSTVT 集和 LASTVT 集

FirstLast 类用于 FIRSTVT 集合和 LASTVT 集合构造。

主要数据:

  • first:char[][] 用于存储非终结符的 FIRSTVT 集合

  • last:char[][] 用于存储非终结符的 LASTVT 集合

对 FIRSTVT 集的构造我们可以给出一个算法,这个算法基于下面两条规则:

  • 若有产生式 A→a…或 A→Ba…,则 a 属于 FIRSTVT(A),其中 A,B为非终结符,a 为终结符

  • 若 a 属于 FIRSTVT(B)且有产生式 A→B…则有 a 属于 FIRSTVT(A)

为了计算方便,我们建立一个布尔数组 F[m,n](m 为非终结符个数,n 为终结符个数)和一个后进先出栈 STACK。我们将所有的非终结符排序,用的序号,再将所有的终结符排序,用 表示终结符 a 的序号。算法的目的是要合数组每一个元素最终取什满足:F[ , ]的值为真,当且仅当 a 属于 FIRSTVT(A)。至此,显然所有非终结符的 FIRSTVT 集己完全确定。

步骤如下:

  • 首先按规则(1)对每个数组元素赋初值。观察这些初值,若 F [ Ai , aj ]的值为真,则将(A ,a)推入栈中,直至对所有数组元素的初值都按此处处理完

  • 然后对栈做以下运算

  • 将栈顶项弹出,设为(B,a),再用规则(2)检查所有产生式,若有形为 A→B…的产生式,而 F [ Ai , aj ]的值是假,则令其变为真,且将(A ,a)推进栈,如此重复直到栈弹空为止

具体的算法可用程序描述为:

  1. PROCEDURE INSERT(Aa)
  2. IF NOT F [ Ai aj ] THEN
  3. BEGIN
  4. F[ Ai aj ]:=TRUE
  5. PUSH(A,a) ONTO STACK
  6. END

此过程用于当 a 属于 FIRSTVT(A)时置 F[ Ai, aj ]为真,并将符号对(A, a)下推到栈中,其主程序为:

  1. BEGIN MAIN
  2. FOR I 1 m,j 1 n
  3. DO F[ Ai aj ] :=FALSE
  4. FOR 每个形如 Aa…或 ABa…的产生式
  5. DO INSERTAa
  6. WHILE STACK 非空 DO
  7. BEGIN
  8. STACK 的顶项记为(Ba)弹出去
  9. FOR 每个形如 AB…的产生式
  10. DO INSERTAa
  11. END
  12. END MAIN

利用类似的方法可求得每个非终结符的 LASTVT(A)。

5.2 由 LASTVT 和 FIRSTVT 集建立优先矩阵

Table 类利用之前构造的 LASTVT 和 FIRSTVT 生成。

主要数据:

  • table: int[][] 用于存储算符优先关系矩阵

有了文法中的每个非终结符的 FIRSTVT 集和 LASTVT 集,我们就可以用如下算法最后构造文法的优先关系表:

  1. FOR 每个产生式 A X1 X2 Xn DO
  2. FOR i:=1 TO n-1 DO
  3. BEGIN
  4. IF Xi Xi+1均为终结符
  5. THEN Xi = Xi+1
  6. IF Xi Xi+2都为终结符,但 Xi+1为非终结符
  7. THEN Xi = Xi+2
  8. IF Xi 为终结符而 Xi+1为非中介符
  9. THEN FOR FIRSTFVT( Xi+1 )中的每个 b DO Xi <b
  10. IF Xi 为非终结符而 Xi+1为终结符
  11. THEN FOR LASTVT( Xi )中的每个 a DO a> Xi+1
  12. END

以上算法对任何算符文法 G 可自动构造其算符优先关系表,并可判断 G 是否为算符优先关系。

5.3 算符文法的分析归约过程算法

自底向上的算符优先分析法,也为自左右向右归约,我们已经知道它不是规范归约。规范归约的关键问题是如何寻找当前句型的句柄,句柄为某一产生式的右面部,归约结果为用与句柄相同的产生式右面部之左部非终结符代替句柄,而算符优先分析归约的关键,是如何找最左素短语,而最左右素短语 Ni ai Ni+1。

ai+1…… aj Nj+1应满足:

  • ai-1 <· ai

  • ai = ai+1 =…… aj

  • aj ·> aj+1

在文法的产生式中存在右面部符号串的符号个数与该素短语的符号个数相等,非终结符号对应 Nk ,(k=i,…,j+1)不管其符号名是什么。终结符对应 i a ,…, j a ,其符号表示要与实际的终结符相一致才有可能形成素短语。由此,我们在分析过程中可以设置一个符号栈 S,用以寄存归约或待形成最左素短语的符号串,用一个工作单元 a 存放当前读入的终结符号,归约成功的标志是当读到句子结束符#时,S 本中只剩#N,即只剩句子最左括号“#”和一非终结符 N。下面给出分析过程的示意图 在归约时要检查是否有对应产生式的右部与 S[j+1]…S[k]形式相符,(忽略非终结符名的不同)若有才可归约,否则出错。在这个分析过程中把“#”也放在终结符串中。

算符优先分析的移进规约流程图:

5.4 语法分析树

语法树是在对字串进行算符优先分析时同步生成的,一个子树对应一个最左速短语。语法树的每一次构建操作对应算符优先分析时的一个规约操作。

语法树根据算符优先规约的规则和逻辑,以自下而上的顺序生成每次算符优先分析时要对 S[j+1]…S[k]规约为某个 N 时,记录下要规约的 S[j+1]…S[k]字符作为当前一个子树的叶子节点,N 作为当前子树的根节点建立父子关系。

将 S[j+1]…S[k]规约成的 N,存入一个栈中(代码中使用一个指针数组实现),保存下来,作为之后规约操作时一个子树的叶节点。

循环执行后,在最后一步规约时,将 S[j+1]…S[k]规约成的 N 作为语法树的根节点 root。

将建立好的语法树逻辑结构,带入多叉树建立算法中,生成语法树,并打印出来。

六、运行截图

七、实验总结

在算符优先文法的程序设计过程中,程序比较复杂,光数据结构设计阶段就占据了很长的时间,几种数据结构很难确定那种能满足程序要求。一旦确定了数据结构,程序编写还是比较顺利。很快程序就可以对正确的输入做出正确的处理,不过没有查错纠错的能力,之后加入查错纠错的功能花费了很大的力气。对整个编程的过程把握的不是很好,以致调试很艰难。

上传的附件 cloud_download 基于C++实现的算符优先文法分析.7z ( 680.08kb, 1次下载 )
error_outline 下载需要8点积分

发送私信

放空的心,是最好的礼物;独走的路,是最美的风景

12
文章数
14
评论数
最近文章
eject