Псевдокод парсера рекурсивного спуска из BNF

Хорошо, я подумал, что здесь будет достаточно специалистов по 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

Это правильно? Я думал, что мне может понадобиться возврат в каждой процедуре, и я тоже не уверен в правильности своей процедуры. Может быть, включить процедуру завершения? В любом случае, большое спасибо! :-)


parsing recursion bnf
person jeppy7    schedule 03.03.2015    source источник
comment
Почему бы вам не закодировать/запустить его и не узнать?   -  person Ira Baxter    schedule 03.03.2015

Ответы (1)


arrow_upward
1
arrow_downward

Вы на полпути. В частности, вы не учитываете леворекурсивные части грамматики, как в "EXP ::= EXP..." или "TERM ::= TERM...".

В любом случае, рекурсивный спуск не совсем подходит для левой рекурсии, но, к счастью, в грамматике можно выполнить стандартные преобразования, которые устранят этот вид левой рекурсии. Например, следующая грамматика:

A ::= A x B | B

можно было бы закодировать так:

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

Более того, код фактора не соответствует грамматике правильно. Обратите внимание, что в первом варианте EXP вызывается рекурсивно (это своего рода рекурсия, с которой рекурсивный спуск не имеет проблем), и вместо этого вы вызываете factor. Кроме того, вы сопоставляете правильные скобки, как если бы это было необязательным, хотя на самом деле это требуется. Та же проблема существует в коде для DIGIT. Если не совпадают ни 0, ни 1, ни 2, должно совпасть 3.

person Branco Medeiros    schedule 03.03.2015
comment
Спасибо за ваш ответ @Branco! Я добавил else break в exp() и term() и думаю, что исправил допущенные ошибки. Я думаю, что я все еще сопоставляю правую скобку и 3, но только без оператора if, верно? Я изменил вызов factor на exp в процедуре factor(). Не могли бы вы бросить последний взгляд. Мы сдали, но кодирование будет к концу семестра. Я также хочу создать для него мобильное приложение :-) - person jeppy7; 04.03.2015