Не могу понять, почему Bison выбрасывает бесполезные правила в парсер из-за конфликтов

Я пишу грамматику BNF для очень простого языка программирования и использую Flex и Bison для компиляции.
У меня есть только 3 типа переменных и констант: real, integer, string.
Мой файл .l содержит определение токена для "ID" следующим образом:

DIGIT [0-9]
LETTER [a-zA-Z]
ID {LETTER}({LETTER}|{DIGIT})*


В моем файле .y есть такое определение идентификатора:

identifier:
ID;

Теперь я хочу использовать определение identifier для создания имен переменных и констант. Но я также хочу ограничить назначение данными одного и того же типа (например, я не хочу, чтобы строка присваивалась целочисленной переменной). Поэтому я создал несколько правил для разделения каждого типа переменных и констант:

id_variable_string:
identifier;

id_variable_integer:
identifier;

id_variable_real:
identifier;

Я сделал то же самое для констант. Теперь в моем языке есть раздел для объявления/определения констант, а затем раздел для объявления переменных. То есть константы объявляются одновременно с их присвоением (что-то вроде «myConstant = 123»), но сначала необходимо объявить переменные, а затем присвоить значение в разделе, специально предназначенном для операторов.
Например, если мне нужно целое число и строковая переменная, я должен сначала объявить их:
STRING myStrVariable;
ЦЕЛОЕ ЧИСЛО myIntVariable;
И затем, в зоне, отведенной для операторов, я могу выбрать выполнение задания (оператор может быть заданием, решением, выбором, выходом и т. д.):

assignment: 
        id_variable_string ASSIGN_OPERATOR literal_string
        | id_variable_string ASSIGN_OPERATOR id_const_string 
        | id_variable_string ASSIGN_OPERATOR id_variable_string 
        | id_variable_string ASSIGN_OPERATOR concatenacion  
        | id_variable_integer ASSIGN_OPERATOR id_const_integer 
        | id_variable_integer ASSIGN_OPERATOR id_variable_integer  
        | id_variable_integer ASSIGN_OPERATOR expression 
        | id_variable_integer ASSIGN_OPERATOR literal_integer
        | id_variable_real ASSIGN_OPERATOR id_variable_real
        | id_variable_real ASSIGN_OPERATOR id_const_real
        | id_variable_real ASSIGN_OPERATOR expression
        | id_variable_real ASSIGN_OPERATOR literal_real
        ;

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

concatenation:
        id_variable_string ADD_OPERATOR id_variable_string 
        | id_variable_string ADD_OPERADOR literal_string 
        | literal_string ADD_OPERADOR id_variable_string 
        | literal_string ADD_OPERADOR literal_string
        | id_const_string ADD_OPERADOR id_const_string  
        | id_const_string ADD_OPERADOR id_variable_string 
        | id_const_string ADD_OPERADOR literal_string 
        | literal_string ADD_OPERADOR id_const_string  
        | id_variable_string ADD_OPERADOR id_const_string
        ;

И выражение определяется как:

expression: 
        expression ADD_OPERATOR term
        | expression SUBST_OPERADOR term
        | term
        ;

term:
        term MULTIP_OPERATOR factor
        | term DIVISION_OPERATOR factor
        | factor
        ;

factor:     
        id_variable_integer
        | id_variable_real
        | id_const_integer
        | id_const_real
        | literal_integer
        | literal_real
        | PARENTHESIS_OPEN expression PARENTHESIS_CLOSE
        ;

Вот что говорит Бизон:


55 назначение: id_variable_integer ASSIGN_OPERATOR id_const_integer
56 | id_variable_integer ASSIGN_OPERATOR id_variable_integer
58 | id_variable_integer ASSIGN_OPERATOR literal_integer
59 | id_variable_real ASSIGN_OPERATOR id_variable_real
60 | id_variable_real ASSIGN_OPERATOR id_const_real
62 | id_variable_real ASSIGN_OPERATOR literal_real


Состояние 50 конфликтов: 1 сдвиг/уменьшение
Состояние 76 конфликтов: 14 сдвиг/уменьшение
Состояние 130 конфликтов: 2 сдвиг/уменьшение
Состояние 131 конфликт: 1 сдвиг/уменьшение
Состояние 133 конфликта : 1 сдвиг/уменьшение
состояние 134 конфликта: 1 сдвиг/уменьшение
состояние 135 конфликтов: 1 сдвиг/уменьшение
состояние 137 конфликтов: 1 сдвиг/уменьшение
состояние 138 конфликтов: 1 сдвиг/уменьшение


Я предполагаю, что что-то в моей грамматике не так, но я не уверен, что именно.


grammar flex-lexer bnf bison
person patr1c1a    schedule 12.11.2013    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Вы сказали:

Поэтому я создал несколько правил для разделения каждого типа переменных и констант:

id_variable_string:
identifier;

id_variable_integer:
identifier;

id_variable_real:
identifier;

И это была твоя проблема. Нет ничего синтаксически, чтобы отличить id_variable_string от id_variable_integer, поэтому у вас есть (по крайней мере, два) бесполезных правила. Вот на это и жалуется. Когда он получает identifier, он понятия не имеет, следует ли рассматривать его как id_variable_string или id_variable_integer.

Вы должны обрабатывать конфликты типов по-другому — семантическая проверка (не синтаксическая проверка), что тип, связанный с идентификатором, совместим с типами других идентификаторов в выражении.

person Jonathan Leffler    schedule 12.11.2013
comment
Спасибо, Джонатан! Когда вы говорите, что мне нужно выполнить семантическую проверку, это выходит за рамки работы, проделанной во flex и bison, верно? Или я еще что-то могу сделать? - person patr1c1a; 12.11.2013
comment
У вас будет проверка в действиях кода Bison, которая гарантирует, что когда у вас есть, скажем, add_expr: identifier '+' identifier {…code…} ; (не очень реалистично, но годится), тогда код проверит, что два идентификатора ($1 и $3 на языке Bison ) определить совместимые типы (обе строки, оба целых числа, оба вещественных числа). «Семантический» означает «неграмматический» (проверки, выходящие за рамки грамматики). Глядя на a + b, это синтаксически правильно, даже если a — строка, а b — вещественное число; это семантическая проверка, которая гарантирует, что имеет смысл попытаться сделать то, что требуется. - person Jonathan Leffler; 12.11.2013
comment
Еще раз спасибо, Джонатан. Что касается грамматики, я пытаюсь заставить ее работать, поэтому я удалил все разные идентификаторы и правила идентификаторов и просто использовал идентификатор токена везде, где был нужен идентификатор. Но Bison все еще жалуется на сдвиг/сокращение в этой части: assignment: ID ASSIGN_OPERATOR ID | ID ASSIGN_OPERATOR literal_integer | ID ASSIGN_OPERATOR literal_real Кажется, это указывает на некоторую проблему в моем факторном правиле (я только заменил каждый другой идентификатор идентификатором токена). Я читаю о сдвиге/уменьшении, используемом Bison, но пока не могу понять, как исправить мою грамматику :/ - person patr1c1a; 12.11.2013
comment
Поскольку я не вижу определений literal_integer и literal_real, трудно понять, что происходит. Однако, поскольку вы, кажется, используете стандартное соглашение о верхнем регистре для токенов и нижнем регистре для правил, похоже, что literal_integer и literal_real являются правилами, и у вас может быть проблема, аналогичная той, что у вас была с вашими идентификаторами - они не различимы грамматически. Вероятно, вам следует исправить это в лексическом анализаторе; он должен возвращать LITERAL_INTEGER и LITERAL_REAL. - person Jonathan Leffler; 12.11.2013
comment
Спасибо, Джонатан. Я обнаружил, что существует еще одна двусмысленность, когда ID ASSIGN_OPERATOR ID также может быть сформирован ID ASSIGN_OPERATOR EXPRESSION, поскольку EXPRESSION может быть сокращен до ID. Я должен исправить почти все ошибки, кроме одной. Я сделал для этого другой пост, потому что объяснение было немного длинным: stackoverflow.com/questions/19942710/. Я также разместил там ссылки на всю грамматику и вывод Bison. Если не сложно и есть желание посмотреть, буду очень признателен :) - person patr1c1a; 13.11.2013