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 }* ) 就會被清理掉 。在一個成功的解析中，整個右邊部分會完全展開來匹配輸入令牌流 。

猜你喜歡