Что делает невозможным использование синтаксического анализатора с рекурсивным спуском без возврата назад, кроме левой рекурсии и двусмысленности? - PullRequest
Новая
       26

Что делает невозможным использование синтаксического анализатора с рекурсивным спуском без возврата назад, кроме левой рекурсии и двусмысленности?

0 голосов
/ 23 мая 2018

Моя первоначальная проблема состояла в том, чтобы выяснить, можно ли проанализировать следующую контекстно-свободную грамматику: grammar_part_1 ; grammar_part_2 ( примеров ) и, если нет, отредактируйте грамматику так, чтобы она была.

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

Теперь есть три решения этой проблемы.проблема:

  1. Грамматика может быть проанализирована парсером рекурсивного спуска без обратного отслеживания.
  2. Задача парсера - подчиняться определению (например, данное правило "нет аналогичного терминального символа-и identif names "), где расширение правила identif с символом терминала идентификации решит проблему.
  3. Существует и другой вид грамматической проблемы, помимо упомянутых.что может произойти с этими синтаксическими анализаторами, о которых я не задумывался.

Предполагая, что моя третья идея верна, какими будут эти методы и, если нет, существуют ли другие методы, чтобы выяснить,грамматика разбирается парсером рекурсивного спуска без возврата назад?Является ли предположение 2 верным?

---------------- РЕДАКТИРОВАТЬ --------------------

Грамматика: 

Prog   -> Def^+
Def    -> DEF Left == Expr
Left   -> MAIN : Type
        | Ident ([Ident:Type(, Ident:Type)^*]):Type
Type   -> NAT
        | BOOL
Expr   -> Num
        | TRUE
        | FALSE
        | Ident[([(Expr(, Expr)^*)])]
        | IF Expr THEN Expr [ELSE Expr] FI
Ident  -> (a|...|z)^+
Num    -> (0|...|9)^+

символов в заглавных буквах (плюс '==', ':', справа от Идентификатор и Num )являются терминалами;(), [], ^ + и ^ * являются операторами обозначений.Отдых нетерминал

1 Ответ

0 голосов
/ 23 мая 2018

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

Более сложная проблема заключается в том, что два нетерминала, чьи наборы FIRST не являются непересекающимися, являются первым символом в разных производствах для одного и того же нетерминала.Хотя форма левостороннего факторинга может работать и в этом случае, нет никакой гарантии, что произвольная контекстно-свободная грамматика может быть проанализирована с помощью анализатора сверху вниз без возврата назад.

...