Связь между грамматикой и ассоциативностью операторов

В некоторых книгах / статьях / статьях по компиляторам говорится о разработке грамматики и взаимосвязи ее операторной ассоциативности. Я большой поклонник нисходящего, особенно рекурсивного спуска, парсеров и до сих пор большинство (если не все) компиляторов, которые я написал, используют следующую грамматику выражений:

Expr   ::= Term { ( "+" | "-" ) Term }
Term   ::= Factor { ( "*" | "/" ) Factor }
Factor ::= INTEGER | "(" Expr ")"

, которая является EBNF-представлением этого BNF:

Expr  ::= Term Expr'
Expr' ::= ( "+" | "-" ) Term Expr' | ε
Term  ::= Factor Term'
Term' ::= ( "*" | "/" ) Factor Term' | ε
Factor = INTEGER | "(" Expr ")"

Судя по тому, что я прочитал, некоторые считают эту грамматику "неправильной" из-за изменения ассоциативности операторов (слева направо для этих 4 операторов), что подтверждается растущим деревом синтаксического анализа справа, а не слева. Для парсера, реализованного с помощью грамматики атрибутов, это может быть правдой, поскольку значение l-атрибута требует, чтобы это значение было сначала создано, а затем передано дочерним узлам. однако при реализации с обычным рекурсивным анализатором спуска мне решать, сначала построить этот узел, а затем перейти к дочерним узлам (сверху вниз) или позволить сначала создать дочерние узлы, а затем добавить возвращаемое значение в качестве дочерних узлов этого узла (передано в конструкторе этого узла) (снизу вверх). Должно быть что-то, что мне здесь не хватает, потому что я не согласен с утверждением, что эта грамматика «неправильная», и эта грамматика использовалась во многих языках, особенно. Виртовские. Обычно (или все?) Чтение, в котором говорится, что продвигает синтаксический анализ LR вместо LL.

6
задан LeleDumbo 2 June 2012 в 07:47
поделиться