Bison/Flex, уменьшить/уменьшить, идентификатор в разных продуктах

Question

Я делаю парсер в бизоне/flex.

Это часть моего кода:

Я хочу осуществить производство присваивания, так что идентификатор может быть как boolean_expr или выражение, его тип будет проверяться с помощью таблицы символов. Так что позволяет что-то вроде:

int a = 1; 
boolean b = true; 
if(b) ... 

Однако свёртка/свёртка, если я включать идентификатор в обоих термина и boolean_expr любое решение, чтобы решить эту проблему?

Answer 1

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

Все равно, как указано, ваша грамматика недвусмысленная и LALR(1). Тем не менее, последняя особенность хрупкая, и вам будет трудно ее поддерживать, когда вы закончите грамматику.

Например, не включают в себя синтаксис присваивания в вашем вопросе, но это было бы

assignment: identifier '=' expr 
      | identifier '=' boolean_expr 
      ; 

В отличие от остальной части грамматики показали, что производство является неоднозначным, так как:

x = y 

не зная ничего о y, y может быть уменьшено до term или boolean_expr.

Возможно, более интересным примером является добавление круглых скобок к грамматике. Очевидный способ сделать это было бы добавить две постановки:

term: '(' expr ')' 

boolean_expr: '(' boolean_expr ')' 

Полученная грамматика не является неоднозначным, но он больше не LALR(1). Рассмотрим две следующие объявления:

boolean x = (y) < 7 
boolean x = (y) 

В первом из них, y должен быть int так, что (y) может быть сведена к term; во втором y должен быть boolean, так что (y) может быть уменьшен до boolean_expr. Нет никакой двусмысленности; как только видят < (или нет), совершенно ясно, какое сокращение выбрать. Но < не-токен, а на самом деле это может быть сколь угодно далеко от y:

boolean x = ((((((((((((((((((((((y... 

Таким образом, в результате чего однозначна грамматика не LALR(k) для любого k.

---

Одним из способов вы могли бы решить эту проблему будут вводить информацию типа на лексическом уровне, путем предоставления доступа сканера к таблице символов.Затем сканер может найти маркер отсканированного идентификатора в таблице символов и использовать информацию в таблице символов для выбора между одним из трех типов токенов (или более, если у вас больше типов данных): undefined_variable, integer_variable и boolean_variable. Тогда вы бы, например:

declaration: "int" undefined_variable '=' expr 
      | "boolean" undefined_variable '=' boolean_expr 
      ; 

term: integer_variable 
    | ... 
    ; 

boolean_expr: boolean_variable 
      | ... 
      ; 

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

Есть языки, для которых это действительно самое удобное решение: например, синтаксический анализ C намного проще, если имена typedef и имена идентификаторов различаются, чтобы вы могли определить, является ли (t)*x актом или умножением. (Но это не так легко для C++, у которого есть гораздо более сложные правила поиска имен, а также гораздо большая потребность в семантическом анализе, чтобы найти правильный синтаксический анализ.)

Но, честно говоря, я бы предложил что вы делаете не использование C - и многое другое C++ - как модель дизайна языка. Языки, которые трудно компилировать для синтаксического анализа, также трудны для разбора человеком. "most vexing parse" продолжает оставаться постоянным источником боли для новичков C++, и даже иногда спотыкаются относительно опытных программистов:

class X { 
    public: 
    X(int n = 0) : data_is_available_(n) {} 
    operator bool() const { return data_is_available_; } 
    // ... 
    private: 
    bool data_is_available_; 
    // ... 
}; 

X my_x_object(); 
// ... 
if (!x) { 
    // This code is unreachable. Can you see why? 
} 

Короче говоря, Вам лучше всего с языком, который может анализироваться в AST без каких-либо семантической информации вообще. После того, как парсер подготовил AST, вы можете выполнять семантический анализ в отдельных проходах, один из которых будет проверять ограничения типов. Это далеко и далеко самое чистое решение. Без явного ввода, грамматика немного упрощена, так как expr теперь может быть любой expr:

expr:  conjunction | expr "or" conjunction ; 
conjunction: comparison | conjunction "and" comparison ; 
comparison: product  | product '<' product ; 
product:  factor  | product '*' factor ; 
factor:  term  | factor '+' term ; 
term:  identifier 
    |  constant 
    |  '(' expr ')' 
    ; 

Каждое действие в вышеуказанном бы просто создать новый узел AST и установить $$ на новый узел. В конце разбора АСТ идет, чтобы проверить, что все expr имеют правильный тип.

Если это кажется излишним для вашего проекта, вы можете выполнять семантические проверки в действиях по сокращению, эффективно смешивая ход AST с синтаксическим разбором. Это может показаться удобным для немедленной оценки, но для этого также требуется включать явную информацию типа в семантическом типе парсера, что добавляет лишние накладные расходы (и, как уже упоминалось, неэффективность допуска семантики вмешивается в парсер.) В этом случае каждое действие будет что-то вроде этого:

expr : expr '+' expr { CheckArithmeticCompatibility($1, $3); 
         $$ = NewArithmeticNode('+', $1, $3); 
        }