遞歸下降解析器來自BNF的僞代碼

Question

好吧，我認爲這裏有足夠的CS專業來檢查我的遞歸下降解析器的僞代碼。我開發從這個BNF

EXP ::= EXP + TERM | EXP - TERM | TERM 
TERM ::= TERM * FACTOR | TERM/FACTOR | FACTOR 
FACTOR ::= (EXP) | DIGIT 
DIGIT ::= 0|1|2|3 

這裏是僞代碼：

procedure exp() 
    term() 
    if token == ‘+’ 
     match(‘+’) 
     term() 
    elseif token == ‘-‘ 
     match(‘-‘) 
     term() 
    else 
     break  

procedure term() 
    factor() 
    if token == ‘*’ 
     match(‘*’) 
     factor() 
    elseif token == ‘/’ 
     match(‘/’) 
     factor() 
    else 
     break 

procedure factor() 
    if token == ‘(‘ 
     match(‘(‘) 
     exp() 
     match(‘)’) 
    else 
     digit() 

procedure digit() 
    if token == ‘0’ 
     match(‘0’) 
    elseif token == ‘1’ 
     match(‘1’) 
    elseif token == ‘2’ 
     match(‘2’) 
    else 
     match(‘3’) 

match(t) 
    if token == t 
     advancetokenpointer 
    else 
     error 

這是正確的嗎？我想我可能需要在每個程序中都有回報，而且我也不確定我的程序是否正確。也許也包括端程序？無論如何，非常感謝！ :-)

Answer 1

你已經走了一半。具體而言，您不會考慮語法的左遞歸部分，如「EXP :: = EXP ...」或「TERM :: = TERM ...」。

無論如何，遞歸下降不太適合左遞歸，但幸運的是，在語法中可以執行標準轉換，這將消除這種左遞歸。作爲一個例子，下面的語法：

A ::= A x B | B 

可以被編碼這樣的：

procedure A() 
    B() 
    repeat 
    if token == 'x' 
     match('x') 
     B() 
    else 
     break 

此外，對於因子的代碼沒有被正確以下語法。注意，在第一種選擇中，EXP被稱爲遞歸（這是一種遞歸下降沒有問題的遞歸），而您正在調用因子。此外，您正確匹配右括號，就好像它是可選的，而實際上它是必需的。 DIGIT代碼中存在同樣的問題。如果0,1或2都不匹配，則3必須匹配。