基于C++实现的语法分析器

Leftme

发布日期: 2021-06-07 09:32:07 浏览量: 97
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

一、环境

  • 运行环境: Windows 10

  • 开发环境:Visual Studio 2017

二、题目

实验内容 - 编写语法分析程序,实现对算术表达式的语法分析。要求所分析算术表达式由如下文法产生:

  1. E -> E+T | E-T | T
  2. T -> T*F | T/F | F
  3. F -> (E) | num

实验要求

  • 在对输入的算术表达式进行分析的过程中,依次输出所采用的产生式

  • 编程实现课本 P92 页的算法 4.2,为给定文法自动构造预测分析表

  • 编程实现课本 P88 页的算法 4.1,构造 LL(1)预测分析程序

三、算法(摘自课本)

3.1 算法 4.1 - 非递归预测分析方法

  • 输入:输入符号串 ω、文法 G 的一张预测分析表 M

  • 输出:若 ω∈L(G)则输出 ω 的最左推导,否则报错

方法

  1. 初始化{
  2. $压入栈底
  3. 将文法开始符号S压入栈顶
  4. 将ω$放入输入缓冲区中
  5. 向前指针ip指向ω$的第一个符号
  6. }
  7. 根据预测分析表M对输入符号串ω做出自顶向下分析{
  8. do {
  9. X是栈顶文法符号,aip指向的符号
  10. if (X是终结符号 || X == '$'){
  11. if (X == a){
  12. 从栈顶弹出X
  13. ip向前移动一个位置
  14. } else {
  15. ERROR
  16. }
  17. } else { // X是非终结符
  18. if (M[X, a] == X -> Y1Y2...Yk){
  19. 从栈顶弹出X
  20. 依次把Yk, Y(k-1), ..., Y1压入栈 // Y1在栈顶
  21. 输出产生式X -> Y1Y2...Yk
  22. } else {
  23. ERROR
  24. }
  25. }
  26. } while (X != '$'); // 栈非空,分析继续
  27. }

3.2 算法 4.2 - 预测分析表的构造方法

  • 输入:文法 G

  • 输出:文法 G 的预测分析表 M

方法

  1. for (文法G的每一个产生式A -> α){
  2. for (每个终结符号aFIRST(α))
  3. A -> α放入表项M[A, a]中
  4. if (ε∈FIRST(α))
  5. for (每个bFOLLOW(A))
  6. A -> α放入表项M[A, b]中
  7. }
  8. for (所有没有定义的表项M[A, a]) 标上错误标识

四、设计与实现

4.1 文法输入

文法输入要求

  • 无环路

  • 无 ε-生成式

文法输入格式

  • 解析时会忽略所有空格和制表符,所以如果为了美观可以添加任意数量的空格和制表符

  • 每行只能有一个非终结符的生成式,但是生成式可以有多个候选式。候选式使用 | 分隔

  • 允许一个非终结符有多行生成式

  • 单个非终结符以大写字母开头,后面可以接任意个英文单引号 '

  • 生成式的左侧只能有一个非终结符,此非终结符后面必须有箭头 ->

  • 只识别每行的第一个箭头 ->,同一行后面还有箭头会视为终结符

  • 字符 ~ 表示 ε,即空串

  • 因为字符 $ 作为分析结束符号,不能出现在文法中,所以使用两个 $ 引起来的字符串被视为一个终结符,如 $num$ 将把 num 视为一个非终结符而不是三个。要求 $ 中的字符串长度大于 1。如果没有使用配对的 $ 而仅使用了单个 $ 则视为错误

  • 上面没有提到的可打印符号均可作为终结符。终结符后面可以接任意个英文单引号 '

  • 默认第一行生成式左侧的非终结符为起始符号

输入示例

  1. E -> E+T | E-T | T
  2. T -> T*F | T/F | F
  3. F -> (E) | $num$

4.2 文法存储

4.2.1 符号的存储

  1. struct Symbol
  2. {
  3. enum SymbolType
  4. {
  5. T, // terminator
  6. NT // non-terminator
  7. };
  8. SymbolType type;
  9. int index; // index in SymbolTable
  10. };

定义了枚举常量 T(终结符)和 NT(非终结符)作为符号类型。定义结构 Symbol,包含一个符号类型 type 和一个在符号表中的索引 index

定义以下两个特殊的终结符:

  1. const Symbol EPSILON = {Symbol::SymbolType::T, 0}; // ε
  2. const Symbol END = {Symbol::SymbolType::T, 1}; // $

严格来说空串 ε 和输入结束符 $ 不算是终结符。此处视为终结符方便管理

4.2.2 符号表

  1. template <bool isTerminatorTable>
  2. class SymbolTable
  3. {
  4. private:
  5. Symbol::SymbolType type;
  6. vector<string> symbols;
  7. public:
  8. SymbolTable();
  9. int getIndex(const string &str); // if str not exist, push it into symbols
  10. int getIndex(const string &str, bool) const; // return -1 if str not exist
  11. string getStr(int i) const; // return blank string if i is invalid
  12. int size() const { return symbols.size(); }
  13. };
  14. using T_Table = SymbolTable<true>;
  15. using NT_Table = SymbolTable<false>;

符号表分为两种:终结符表和非终结符表。其中终结符表在构造时就需要添加符号 $ε。为了方便理解,使用 using 对不同类型的符号表进行了重命名,即 T_Table 和 NT_Table。为了实现以上两点,使用模板来设计符号表,模板参数 isTerminatorTable 表示了此符号表是否是终结符号表。

符号表中并没有保存符号 Symbol,而是保存了每个符号的字符串量,即 vector<string> symbols,所以不能从符号表获得符号,但是可以根据符号的下标来查询字符串量(即 getStr 方法),也可以根据符号的字符串量来查询下标(即 getIndex)。所以符号表只是一个用来查询的表,并不是一个符号的容器。

函数解释

  • int getIndex(const string &str) - 查询字符串并返回下标。如果没有此字符串则插入此字符串

  • int getIndex(const string &str, bool) const - 仅查询字符串并获得下标

  • string getStr(int i) const - 查询对应下标的符号的字符串

  • int size() const - 查询符号表容量

4.2.3 文法表

  1. class GrammaTable
  2. {
  3. private:
  4. // input
  5. vector<Gramma> grammas;
  6. T_Table tTable;
  7. NT_Table ntTable;
  8. // error handling
  9. int lineCount;
  10. bool error;
  11. // process
  12. vector<First> firsts;
  13. vector<Follow> follows;
  14. map<MapKey, TableItem> M; // predict analysis table
  15. void killBlank(string &str) const; // discard blank chars
  16. bool format(string &str) const; // return false if format is wrong
  17. /**
  18. * killDuplicated:
  19. * eliminate same Candidate in grammas[index] if index != -1
  20. * eliminate same Candidate in each Gramma when index == -1
  21. */
  22. void killDuplicated(int index = -1);
  23. void killExplicitLeftRecursion(int index);
  24. void killEpsilon();
  25. void killLeftRecursion();
  26. void getFirsts();
  27. First getFirst(const Candidate &candidate) const;
  28. void getFollows();
  29. bool getM();
  30. Candidate parseInputToCandidate(const string &str) const; // return empty candidate if error
  31. void outputSingleCandidate(int ntIndex, int candidateIndex) const;
  32. public:
  33. GrammaTable() : lineCount(0), error(false){};
  34. int insert(const string &grammaLine); // return 0 if ok, otherwise return lineCount
  35. bool generate(); // return false if error
  36. void output() const;
  37. bool ok() const { return !error; }
  38. int currentLineCount() const { return lineCount; }
  39. bool parse(const string &str) const;
  40. };

文法表包括了文法 grammas、符号表 tTable 和 ntTable、此文法生成的 FIRST 集与 FOLLOW 集和预测分析表 M。

  1. using Candidate = vector<Symbol>;
  2. using Gramma = vector<Candidate>;

一个候选式 Candidate 由若干个符号 Symbol 组成,一个符号的生成式 Gramma 由若干个候选式 Candidate 组成。

  1. using First = set<Symbol>;
  2. using Follow = set<Symbol>;

FIRST 集和 FOLLOW 集是符号 Symbol 的集合。为了使用 std::set,需要给 Symbol 设置 operator< 使其能够比较大小。比大小采取的方案是:使用 Symbol 的 index 作为值,Symbol 的 type 作为值的正负号,这样每一个 Symbol 都会有一个唯一的值。

  1. struct TableItem // item in predict analysis table M
  2. {
  3. int ntIndex = -1; // non-terminator index in grammas
  4. int candidateIndex = -1; // candidate index in grammas[ntIndex]
  5. };
  6. struct MapKey
  7. {
  8. int ntIndex;
  9. int tIndex;
  10. };

预测分析表 map<MapKey, TableItem> M 为一个 key-value 单向映射的表。表的键 MapKey 由一个非终结符(的下标)和一个终结符(的下标)构成,表项 TableItem 由一个非终结符(的下标)和此非终结符生成式的一个候选式(的下标)构成。

为了使用 std::map,需要给 MapKey 设置 operator< 使其能够比较大小。采取的方案是:每个 MapKey 的值等于 ntIndex + 100 * tIndex,这样可以保证小规模输入时每个 MapKey 都会有一个唯一的值。

变量 lineCount 和 error 用来控制错误,当错误发生时不能够继续输入文法、不能生成 FIRST 集和 FOLLOW 集、不能解析输入串。输入错误时会返回 lineCount,根据此值可以定位输入的错误。

函数解释

  • private
    • void killBlank(string &str) const; - 清除输入串中的空白符(空格、制表、换行)
    • bool format(string &str) const; - 如果输入串没有 -> 则报错
    • void killDuplicated(int index = -1); - 清除第 index 个非终结符的重复生成式。index 为-1 时清除所有非终结符的重复生成式
    • void killExplicitLeftRecursion(int index); - 消除第 index 个非终结符生成式中的直接左递归
    • void killEpsilon(); - 清除所有候选式中多余的 ε
    • void killLeftRecursion(); - 消除直接和间接左递归
    • void getFirsts(); - 生成所有非终结符的 FIRST 集
    • First getFirst(const Candidate &candidate) const; - 在所有非终结符的 FIRST 存在的情况下生成单个候选式的 FIRST 集
    • void getFollows(); - 生成所有非终结符的 FOLLOW 集
    • bool getM(); - 生成预测分析表
    • Candidate parseInputToCandidate(const string &str) const; - 把字符串解析为符号串
    • void outputSingleCandidate(int ntIndex, int candidateIndex) const; - 输出单个生成式
  • public
    • int insert(const string &grammaLine); - 插入一行文法。如果文法出错则返回 lineCount,否则返回 0
    • bool generate(); - 生成 FIRST 集、FOLLOW 集和预测分析表,如果生成失败则返回 false
    • void output() const; - 输出消左递归后的文法、FIRST 集、FOLLOW 集、预测分析表
    • bool ok() const { return !error; } - 判断此预测分析表是否能够正常继续输入
    • int currentLineCount() const { return lineCount; } - 返回当前行数,通常用来确定错误发生的位置
    • bool parse(const string &str) const; - 试图解析输入的字符串。如果解析失败则返回 false

4.3 解析串输入

解析串输入的格式和文法的输入类似:

  • 每个解析串只能有一行

  • 解析串只能包含终结符

  • 如果一个终结符包含多个非英文单引号 ' 的字符,则可以像文法串一样使用两个 $ 引起来

  • 解析串中的所有空白字符(空格、换行、制表)会被消除

示例输入:

  1. $num$+$num$*$num$/$num$-$num$

4.4 工作流程设计与实现

  1. 输入文法

  2. 消左递归

  3. 计算 FIRST 集

  4. 计算 FOLLOW 集

  5. 输入文法符号串

  6. 使用预测分析表分析

在 main 函数中的实现:

  1. 文法表gt
  2. 读取一行
  3. while (不是空行且文法表未出错)
  4. {
  5. gt.insert(此行文法);
  6. }
  7. gt.generate();生成消左递归文法、FIRST集、FOLLOW集和预测分析表
  8. gt.output();输出消左递归文法、FIRST集、FOLLOW集和预测分析表
  9. 读取一行
  10. while (不是空行)
  11. {
  12. gt.parse(输入的解析串)
  13. }

其中输入文法时输入空行结束,然后。输入解析串时一次一行,输入空行结束。

五、测试与说明

5.1 输入

输入示例

  1. E -> E+T | E-T | T
  2. T -> T*F | T/F | F
  3. F -> (E) | $num$
  4. // 此处为空行,结束文法串的输入
  5. $num$+$num$*$num$/$num$-$num$
  6. ($num$+($num$-($num$*($num$/($num$)))))
  7. $num$
  8. ($num$+($num$-($num$*($num$/($num$))))
  9. $num$+($num$-($num$*($num$/($num$)))))
  10. ($num$+($num$-($nu*($num$/($num$))))
  11. // 此处为空行,结束解析串的输入

5.2 输出

  1. *************************************************************
  2. Compiler-Grammatical-Analyzer(CGA)
  3. Written By DiscreteTom
  4. *************************************************************
  5. Please input grammas.
  6. Input blank line to stop input.
  7. E -> E+T | E-T | T
  8. T -> T*F | T/F | F
  9. F -> (E) | $num$
  10. Output:
  11. Format gramma:
  12. E -> TE'
  13. T -> FT'
  14. F -> (E) | num
  15. E' -> +TE' | -TE' | ~
  16. T' -> *FT' | /FT' | ~
  17. First:
  18. First(E): ( num
  19. First(T): ( num
  20. First(F): ( num
  21. First(E'): ~ + -
  22. First(T'): ~ * /
  23. Follows:
  24. Follow(E): $ )
  25. Follow(T): $ + - )
  26. Follow(F): $ + - * / )
  27. Follow(E'): $ )
  28. Follow(T'): $ + - )
  29. Predict Analyze Table:
  30. [E', ~]: E' -> ~
  31. [T', ~]: T' -> ~
  32. [E', $]: E' -> ~
  33. [T', $]: T' -> ~
  34. [E', +]: E' -> +TE'
  35. [T', +]: T' -> ~
  36. [E', -]: E' -> -TE'
  37. [T', -]: T' -> ~
  38. [T', *]: T' -> *FT'
  39. [T', /]: T' -> /FT'
  40. [E, (]: E -> TE'
  41. [T, (]: T -> FT'
  42. [F, (]: F -> (E)
  43. [E', )]: E' -> ~
  44. [T', )]: T' -> ~
  45. [E, num]: E -> TE'
  46. [T, num]: T -> FT'
  47. [F, num]: F -> num
  48. Input a line to parse, input blank line to stop.
  49. $num$+$num$*$num$/$num$-$num$
  50. Use: E -> TE'
  51. Use: T -> FT'
  52. Use: F -> num
  53. Use: T' -> ~
  54. Use: E' -> +TE'
  55. Use: T -> FT'
  56. Use: F -> num
  57. Use: T' -> *FT'
  58. Use: F -> num
  59. Use: T' -> /FT'
  60. Use: F -> num
  61. Use: T' -> ~
  62. Use: E' -> -TE'
  63. Use: T -> FT'
  64. Use: F -> num
  65. Use: T' -> ~
  66. Use: E' -> ~
  67. Accept.
  68. Input a line to parse, input blank line to stop.
  69. ($num$+($num$-($num$*($num$/($num$)))))
  70. Use: E -> TE'
  71. Use: T -> FT'
  72. Use: F -> (E)
  73. Use: E -> TE'
  74. Use: T -> FT'
  75. Use: F -> num
  76. Use: T' -> ~
  77. Use: E' -> +TE'
  78. Use: T -> FT'
  79. Use: F -> (E)
  80. Use: E -> TE'
  81. Use: T -> FT'
  82. Use: F -> num
  83. Use: T' -> ~
  84. Use: E' -> -TE'
  85. Use: T -> FT'
  86. Use: F -> (E)
  87. Use: E -> TE'
  88. Use: T -> FT'
  89. Use: F -> num
  90. Use: T' -> *FT'
  91. Use: F -> (E)
  92. Use: E -> TE'
  93. Use: T -> FT'
  94. Use: F -> num
  95. Use: T' -> /FT'
  96. Use: F -> (E)
  97. Use: E -> TE'
  98. Use: T -> FT'
  99. Use: F -> num
  100. Use: T' -> ~
  101. Use: E' -> ~
  102. Use: T' -> ~
  103. Use: E' -> ~
  104. Use: T' -> ~
  105. Use: E' -> ~
  106. Use: T' -> ~
  107. Use: E' -> ~
  108. Use: T' -> ~
  109. Use: E' -> ~
  110. Use: T' -> ~
  111. Use: E' -> ~
  112. Accept.
  113. Input a line to parse, input blank line to stop.
  114. $num$
  115. Use: E -> TE'
  116. Use: T -> FT'
  117. Use: F -> num
  118. Use: T' -> ~
  119. Use: E' -> ~
  120. Accept.
  121. Input a line to parse, input blank line to stop.
  122. ($num$+($num$-($num$*($num$/($num$))))
  123. Use: E -> TE'
  124. Use: T -> FT'
  125. Use: F -> (E)
  126. Use: E -> TE'
  127. Use: T -> FT'
  128. Use: F -> num
  129. Use: T' -> ~
  130. Use: E' -> +TE'
  131. Use: T -> FT'
  132. Use: F -> (E)
  133. Use: E -> TE'
  134. Use: T -> FT'
  135. Use: F -> num
  136. Use: T' -> ~
  137. Use: E' -> -TE'
  138. Use: T -> FT'
  139. Use: F -> (E)
  140. Use: E -> TE'
  141. Use: T -> FT'
  142. Use: F -> num
  143. Use: T' -> *FT'
  144. Use: F -> (E)
  145. Use: E -> TE'
  146. Use: T -> FT'
  147. Use: F -> num
  148. Use: T' -> /FT'
  149. Use: F -> (E)
  150. Use: E -> TE'
  151. Use: T -> FT'
  152. Use: F -> num
  153. Use: T' -> ~
  154. Use: E' -> ~
  155. Use: T' -> ~
  156. Use: E' -> ~
  157. Use: T' -> ~
  158. Use: E' -> ~
  159. Use: T' -> ~
  160. Use: E' -> ~
  161. Use: T' -> ~
  162. Use: E' -> ~
  163. Input not belongs to this gramma.
  164. Input a line to parse, input blank line to stop.
  165. $num$+($num$-($num$*($num$/($num$)))))
  166. Use: E -> TE'
  167. Use: T -> FT'
  168. Use: F -> num
  169. Use: T' -> ~
  170. Use: E' -> +TE'
  171. Use: T -> FT'
  172. Use: F -> (E)
  173. Use: E -> TE'
  174. Use: T -> FT'
  175. Use: F -> num
  176. Use: T' -> ~
  177. Use: E' -> -TE'
  178. Use: T -> FT'
  179. Use: F -> (E)
  180. Use: E -> TE'
  181. Use: T -> FT'
  182. Use: F -> num
  183. Use: T' -> *FT'
  184. Use: F -> (E)
  185. Use: E -> TE'
  186. Use: T -> FT'
  187. Use: F -> num
  188. Use: T' -> /FT'
  189. Use: F -> (E)
  190. Use: E -> TE'
  191. Use: T -> FT'
  192. Use: F -> num
  193. Use: T' -> ~
  194. Use: E' -> ~
  195. Use: T' -> ~
  196. Use: E' -> ~
  197. Use: T' -> ~
  198. Use: E' -> ~
  199. Use: T' -> ~
  200. Use: E' -> ~
  201. Use: T' -> ~
  202. Use: E' -> ~
  203. Input not belongs to this gramma.
  204. Input a line to parse, input blank line to stop.
  205. ($num$+($num$-($nu*($num$/($num$))))
  206. Invalid input.
  207. Input a line to parse, input blank line to stop.
  208. 请按任意键继续. . .

输出解释

  • 开发者信息

  • 输入的三行文法串

  • 消左递归后的文法

  • 所有非终结符的 FIRST 集

  • 所有非终结符的 FOLLOW 集

  • 预测分析表(以键值对的方式输出表项)

  • 输入的解析串

  • 解析此串使用的生成式

  • 解析成功(Accept)

  • 输入的解析串

  • 解析此串使用的生成式

  • 解析成功(Accept)

  • 输入的解析串

  • 解析此串使用的生成式

  • 解析成功(Accept)

  • 输入的解析串

  • 解析此串使用的生成式

  • 解析失败(Input not belongs to this gramma)

    • 因为输入少了一个右括号
  • 输入的解析串

  • 解析此串使用的生成式

  • 解析失败(Input not belongs to this gramma)

    • 因为输入少了一个左括号
  • 输入的解析串

  • 解析此串使用的生成式

  • 解析失败(Invalid input)

    • 因为输入时输入了不在符号表中的终结符

5.3 运行截图

初始状态

输入文法后

输入正确串并成功解析

输入错误串并解析报错

输入空行结束程序

上传的附件 cloud_download 基于C++实现的语法分析器.7z ( 137.24kb, 1次下载 )
error_outline 下载需要11点积分

发送私信

告别错的,方可遇见对的

18
文章数
17
评论数
最近文章
eject