自顶向下的语法分析器

一、问题及解决：

• 什么是Dictionary File？

   这种类型的文件为Windows虚拟PC 2007，虚拟机，它允许一些版本的Windows在一台计算机上运行生成。它包括像发音和单词的定义以及各种语言，如德国和法国的辞典数据。

• 如何实现语法分析器？

  • 词法分析器

    • 在 $clang.lex$ 增补需要识别的词法单元(do、while、%)，并在 $lex.yy.h$ 定义（%需要转义[%%])
    • 这里对 ‘%’ 做了简化，按照与 *、/ 同优先级处理，实际优先级：乘除（*/）>取余（%）> 加减（+ -）

  • 左递归和公共左因子的处理

    • $parser.cpp$ 初始版本的处理存在左递归和公共左因子，需要改造成$LL(1)$文法（消除递归可以进一步化简）

  • First集与Follow集

    • 注意产生式符合$A->\alpha B\beta ,\beta ->ϵ$ 的情况，要将follow(A)加到follow(B)中

      C →+ term C | - term C | ɛ 
      

  • 预测分析器

    • 编译

    ./flex clang.tex  /*更新*/
    gcc lex.yy.c parser.cpp -o p    /*两个文件一起*/
    

    • 运行

    ./flex clang.lex
    

  • if语句二义性的处理

    • 对提取左公因子的式子：

      ​ stmt → if ( bool ) stmt else_part | 其它语句

      ​ else_part → else stmt | ɛ

      如果 $lookahead$ 是词法单元$else$时，使用产生式 $else\_part\to elsestmt$；否则使用产生式 $else\_part\to ϵ$

二、实验结果：

程序片断：

{
i = 2;
   sum = 0;
   while (i <=100) {
      sum = sum + i;
   i = i + 2;
          if(i%50==0) break;
   }
}

打印产生式如下：

附：

提取公共左因子：

program → block
block →{ stmts }
stmts →  stmt stmts | ɛ
stmt →id = expr ; 
        |if ( bool ) stmt A
        |while (bool) stmt 
        |do stmt while (bool ) ; 
        |break; 
        |block
 A→else stmt | ɛ
bool → expr B
 B → relop expr | ɛ
expr → expr C | term
 C →   + term | - term 
term → term D | factor
 D → * factor | / factor | % factor
factor→ ( expr ) | id | num

消除直接左递归：

program → block
block →{ stmts }
stmts →  stmt stmts | ɛ
stmt →id = expr ; 
        |if ( bool ) stmt A
        |while (bool) stmt 
        |do stmt while (bool ) ; 
        |break; 
        |block
 A→else stmt | ɛ
bool → expr B
 B → relop expr | ɛ
expr → term C
 C→+ term C  | - term C | ɛ 
term →factor D
 D→* factor D | / factor D| % factor D| ɛ 
factor→ ( expr ) | id | num

First集：

first(program) = first(block) = {'{'};
first(stmts) = first{id, if, while, do, break, '{', ɛ};
first(stmt) = {id, if, while, do, break, '{'};
first(A) = {else, ɛ};
first(bool) = first(expr) = first(term) = first(factor) = {'(', id, num};
first(B) = {relop, ɛ};
first(C) = {+, -, ɛ};
first(D) = {*, /, %, ɛ};

Follow集：

follow(program) = {$};
follow(block) = {$, id, if, while, do, break, '{', '}', else};
follow(stmts) = {'}'};
follow(stmt) = {id, if, while, do, break, '{', '}', else};
follow(A) = {id, if, while, do, break, '{', '}', else, '}'};
follow(bool) = {')'};
follow(B) = {')'};
follow(expr) = {relop, ';', ')'};
follow(C) = {relop, ';', ')'};
follow(term) = {+, -, relop, ';', ')'};
follow(D) = {+, -, relop, ';', ')'};
follow(factor) = {+, -, relop, ';', ')', *, /, %};

原文地址：https://blog.csdn.net/qq_38236082/article/details/137741001

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！