Столкновение между "END" и "END IF" в грамматике BASIC, используя Lark - PullRequest
Новая
       50

Столкновение между "END" и "END IF" в грамматике BASIC, используя Lark

1 голос
/ 10 мая 2019

Я пытаюсь создать парсер LALR для BASIC, используя Lark , и мне трудно исправить коллизию между оператором "END" и операторами, такими как "END IF".Вот упрощенная версия грамматики: 

%ignore /[ \t\f]+/

program: _nlopt _part_list

_part_list: (stmt | block) _nl _part_list
          |

_nlopt: _nl
      |

_nl: _NEWLINE _nl
   | _NEWLINE

block: if_block

stmt: print_stmt
    | end_stmt

end_stmt: END_KW

if_block: IF_KW expr THEN_KW _nl block_body endif_stmt

endif_stmt: END_KW IF_KW

block_body: _block_body_item block_body
          |

_block_body_item: stmt _nl

print_stmt: PRINT_KW expr

?expr: NUMERIC_LITERAL

_NEWLINE: "\n"
NUMERIC_LITERAL: /[\-+]?\d+(\.\d*)?[!#%&]?/

END_KW: "end"i
IF_KW: "if"i
PRINT_KW: "print"i
THEN_KW: "then"i

Если я попробую эту грамматику с кодом, подобным этому: 

parser = Lark(grammar, start='program', parser='lalr')

prog = r"""
if 1 then
   print 200
end if
"""
t = parser.parse(prog)
print(t.pretty())

Вот что я получаю от Ларк: 

Traceback (most recent call last):
  File "test.py", line 230, in <module>
    t = parser.parse(prog)
  File "/home/user/.pyenv/versions/venv/lib/python3.6/site-packages/lark/lark.py", line 250, in parse
    return self.parser.parse(text)
  File "/home/user/.pyenv/versions/venv/lib/python3.6/site-packages/lark/parser_frontends.py", line 37, in parse
    return self.parser.parse(token_stream, *[sps] if sps is not NotImplemented else [])
  File "/home/user/.pyenv/versions/venv/lib/python3.6/site-packages/lark/parsers/lalr_parser.py", line 68, in parse
    for token in stream:
  File "/home/user/.pyenv/versions/venv/lib/python3.6/site-packages/lark/lexer.py", line 341, in lex
    for x in l.lex(stream, self.root_lexer.newline_types, self.root_lexer.ignore_types):
  File "/home/user/.pyenv/versions/venv/lib/python3.6/site-packages/lark/lexer.py", line 175, in lex
    raise UnexpectedCharacters(stream, line_ctr.char_pos, line_ctr.line, line_ctr.column, allowed=allowed, state=self.state)
lark.exceptions.UnexpectedCharacters: No terminal defined for 'i' at line 4 col 5

end if
    ^

Expecting: ['__IGNORE_0', '_NEWLINE']

Если я удалю правило "end_stmt", этого не произойдет.Есть ли способ исправить грамматику, чтобы этого не произошло?

Ответы [ 2 ]

3 голосов
/ 11 мая 2019

По умолчанию Ларк не предупреждает вас о конфликтах сдвига-уменьшения в грамматике и вместо этого молча разрешает их в пользу сдвига.Часто это приводит к синтаксическому анализатору, который не выполняет синтаксический анализ того, что вы хотите - как в данном случае.Вы можете заставить lark предупредить вас о подобных конфликтах, передав флаг debug = True в Lark().Таким образом, вы увидите, что что-то не так, даже прежде, чем обнаружите проблему с помощью тестов, и вы можете даже получить полезную информацию о том, где находится проблема.

С включенной опцией debug вы получите предупреждениеэто конфликт сдвига-уменьшения, где END_KW может означать, что текущий block_body закончился, или это может быть end_stmt.Это проблема, потому что синтаксический анализатор LALR (1) может просматривать только один токен вперед, но нам нужно посмотреть второй токен вперед, чтобы увидеть, есть ли if после end, чтобы правильно решить, какой вариант выбрать.

Вы можете исправить это, немного хакерски, превратив end if в один токен, подобный этому: 

ENDIF_KW: /end[ \t\f]+if/i

И затем использовать ENDIF_KW вместо END_KW IF_KW.

PS: обратите внимание, что ваша грамматика будет работать без этих изменений, если вы используете разбор Earley вместо LALR (1).

1 голос
/ 22 мая 2019

У меня был тот же конфликт с моей основной грамматикой.Базовым языком является LALR (2) или LR (2) из-за END WHILE, END IF и т. Д. Если у вас есть генератор синтаксического анализатора LR (2), вы можете анализировать базовый.Генератор парсера LRSTAR может создавать парсеры LR (2).

...