Уменьшить / уменьшить конфликт при введении указателей в мою грамматику

Question

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

Вот упрощенная версия моей грамматики, которая компилируется bnfc, Я использую happy Генератор синтаксического анализатора, и это программа, которая сообщает мне, что существует конфликт уменьшения / уменьшения.

entrypoints Stmt ;

-- Statements
-------------
SDecl. Stmt ::= Type Ident; -- ex: "int my_var;"
SExpr. Stmt ::= Expr;       -- ex: "printInt(123); "

-- Types
-------------
TInt.      Type ::= "int" ;
TPointer.  Type ::= Type "*" ;
TAlias.    Type ::= Ident ; -- This is how I implement typedefs

-- Expressions
--------------
EMult.     Expr1 ::= Expr1 "*" Expr2 ;
ELitInt.   Expr2 ::= Integer ;
EVariable. Expr2 ::= Ident ;

-- and the standard corecions
_.         Expr  ::= Expr1 ;
_.         Expr1 ::= Expr2 ;

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

main(){
  int a;
  int b;
  a * b;
}

а также

typedef int my_type;
main(){
  my_type * my_type_pointer_variable;
}

(The typedef а также main(){} часть не актуальна и в моей грамматике. Но они дают некоторый контекст)

В первой программе хотелось бы разобрать a "*" b как Stmt ==(SExpr)==> Expr ==(EMult)==> Expr * Expr ==(..)==> Ident "*" Identто есть по сути начать шагать с помощью SExpr править.

В то же время я хотел бы my_type * my_type_pointer_variable быть расширенным с использованием правил. Stmt ==(SDecl)==> Type Ident ==(TPointer)==> Type "*" Ident ==(TAlias)==> Ident "*" Ident,

Но на этапе грамматики понятия не имею, является ли идентификатор изначально псевдонимом типа или переменной.

---

(1) Как я могу избавиться от конфликта "уменьшить / уменьшить" и (2) я единственный, у кого есть эта проблема? Есть ли очевидное решение и как грамматика c решает эту проблему?

До сих пор я только что смог изменить синтаксис моего языка, используя "&" или другой символ вместо "*", но это очень нежелательно. Также я не могу понять смысл различных публичных грамматик и пытался понять, почему у них нет этой проблемы, но мне не повезло в этом.

И наконец, как я могу решить подобные проблемы самостоятельно? Все, что я понял из happyБолее подробный вывод о том, как происходит конфликт, является ли хитрость единственным способом обойти эти конфликты? Боюсь, что наткнусь на еще больше вопросов, например, при представлении EIndir. Expr = '*' Expr;

Answer 1

Обычный способ решения этой проблемы в синтаксических анализаторах C - это то, что обычно называют "хакером обратной связи лексера". Это "взлом" в том смысле, что в грамматике он вообще не имеет к этому отношения; вместо этого, когда лексер распознает идентификатор, он классифицирует этот идентификатор как typename или non-typename и возвращает различный токен для каждого случая (обычно обозначается "TypeIdent" для идентификатора, который является typename, и просто "Ident" для любой другой). Лексер делает этот выбор, просматривая текущее состояние таблицы символов, поэтому он видит все определения типов, которые произошли до текущей точки в разборе, но не определения типов, которые идут после текущей точки. Вот почему C требует, чтобы вы объявляли typedef перед их первым использованием в каждом модуле компиляции.