湖南龙网

  1. 首页 > 生活百科 > >

编译原理递归下降分析程序 递归下降分析法

生活百科语法


你想根据一组语法规则解析文本并执行命令，或者构造一个代表输入的抽象语法树 。如果语法非常简单，你可以自己写这个解析器，而不是使用一些框架 。
在这个问题中，我们集中讨论根据特殊语法去解析文本的问题 。为了这样做，你首先要以 BNF(巴科斯范式)或者 EBNF(扩展巴科斯范式)形式指定一个标准语法 。
具体关于BNF和EBNF的介绍，可以查看中国维基百科：
BNF：
https://zh.wikipedia.org/wiki/巴科斯范式
【编译原理递归下降分析程序 递归下降分析法】EBNF：
https://zh.wikipedia.org/wiki/扩展巴科斯范式
比如，一个简单数学表达式语法可能像下面这样：
expr ::= exprterm| expr - term| termterm ::= term * factor| term / factor| factorfactor ::= ( expr )| NUM 或者，以 EBNF 形式：
expr ::= term { ( |-) term }*term ::= factor { (*|/) factor }*factor ::= ( expr )| NUM BNF形式简单，知道终结符和非终结符，并且知道 三个符号：
“::=”，表示定义为
“|”，表示或
“<>”，用来区分非终结符
EBNF多增加几个符号：
“[]”,表示可选项
“{}”，表示重复0次或者多次
引号本身，便于区分单个符号的终结符
在 EBNF 中，被包含在 {…}* 中的规则是可选的 。*代表 0 次或多次重复 (跟正则表达式中意义是一样的) 。
上边例子中更加易读的写法应该是：
# 加个<>尖括号表示非终结符 ::= | - | ::= * | / | ::= ( )| NUM BNF例子，如正则表达式：”a(bb)*c”
::=a::=bb|c 现在，如果你对 BNF 的工作机制还不是很明白的话，就把它当做是一组左右符号可相互替换的规则 。一般来讲，解析的原理就是你利用 BNF 完成多个替换和扩展以匹配输入文本和语法规则 。为了演示，假设你正在解析形如 23 * 4 的表达式 。这个表达式先要通过使用介绍过的令牌解析技术分解为一组令牌流 。结果可能是像下列这样的令牌序列：
NUMNUM * NUM 在此基础上，解析动作会试着去通过替换操作匹配语法到输入令牌：
exprexpr ::= term { ( |-) term }*expr ::= factor { (*|/) factor }* { ( |-) term }*expr ::= NUM { (*|/) factor }* { ( |-) term }*expr ::= NUM { ( |-) term }*expr ::= NUMterm { ( |-) term }*expr ::= NUMfactor { (*|/) factor }* { ( |-) term }*expr ::= NUMNUM { (*|/) factor}* { ( |-) term }*expr ::= NUMNUM * factor { (*|/) factor }* { ( |-) term }*expr ::= NUMNUM * NUM { (*|/) factor }* { ( |-) term }*expr ::= NUMNUM * NUM { ( |-) term }*expr ::= NUMNUM * NUM 下面所有的解析步骤可能需要花点时间弄明白，但是它们原理都是查找输入并试着去匹配语法规则 。第一个输入令牌是 NUM，因此替换首先会匹配那个部分 。一旦匹配成功，就会进入下一个令牌，以此类推 。当已经确定不能匹配下一个令牌的时候，右边的部分 (比如 {(*/)factor }* ) 就会被清理掉 。在一个成功的解析中，整个右边部分会完全展开来匹配输入令牌流 。

推荐阅读


上一篇：吃热的牙疼怎么回事 吃热的牙疼的原因

下一篇：电脑原神怎么拿鱼竿 电脑原神如何拿鱼竿呢