FeelUs Sep 10 2015 at 12:27

Способ написания синтаксических анализаторов на c++

11 min

31K

Programming*C++*Algorithms*

From sandbox

+13

Comments 29

roman_kashitsyn Sep 10 2015 at 12:44

Я правильно понимаю, что вы описали Recursive Descent Parser?

FeelUs Sep 10 2015 at 20:06

да
стандартная библиотека си (да и с++ наверно) дает возможность реализовывать LL(1) грамматики (при помощи ungetc())
а forward_stream дает возможность реализовывать LL(*) грамматики

leshabirukov Sep 10 2015 at 14:39

Вот есть грамматика:

...
expr ::= expr '+' expr
expr ::= expr '-' expr
expr ::= expr '*' expr
expr ::= expr '/' expr

Разберите строку
( A + B +… * X ) / Z
Каждое из четырёх правил начнёт применяться, но три раза придётся откатывать, то есть выражение в скобках будет распарсено четырежды.

Написать хороший парсер не так-то просто и С для этой задачи подходит плохо, поэтому-то живут и здравствуют такие инструменты как flex+bison, boost::spirit и прочие.

mayorovp Sep 10 2015 at 14:56

Это — недостаток грамматики, а не подхода. Вот правильная грамматика:

  multiplier ::= ... | '(', expr, ')'.
  addendum ::= multiplier, { ('*' | '/'), addendum }.
  expr ::= addendum, { ('+' | '-'), expr }.

Orient Sep 11 2015 at 07:17

Можно ещё дальше пойти и (в ваших терминах) сделать так: expr ::= expr, { ('+' | '-' | '*' | '/'), expr } а затем применить алгоритм сортировочной станции, чтобы достроить поддеревья для подвыражений с двуместными операциями (вот пример грамматики в Boost.Spirit X3 и пример применения алгоритма сортировочной станции для «допарсивания» выражения).

leshabirukov Sep 11 2015 at 18:12

Да, я наверное неудачный привёл пример, но для более или менее сложной грамматики всё-таки стоит использовать генератор парсеров.

FeelUs Sep 10 2015 at 20:20

KvanTTT Sep 10 2015 at 15:04

Таким образом для написания парсера не требуется умения обращаться с другими программами генерации парсеров.

Ну и какое в этом преимущество? Зато у вас парсер сильно зависит от языка реализации.

Я конечно понимаю, что иногда нужно создавать собственный велосипед. Но, честно говоря, лучше бы вы все же использовали ANTLR для описания грамматики и дорабатывали рантайм под C++: antlr4-cpp. У него куча грамматик еще реализована, причем в более лаконичном формате EBNF.

FeelUs Sep 16 2015 at 10:16

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

KvanTTT Sep 17 2015 at 13:10

Нужно изучать инструмент, который используешь. В ANTLR система обработки ошибок достаточно сильно продумана, например при отсутствующем токене, он может «достроиться» сам, чтобы в данном участке кода парсер детектировал только одну ошибку, а не множество.
В книге по ANTLR есть отдельная глава, посвященная обработке ошибок.

FeelUs Sep 17 2015 at 21:06

о, кстати можно добавить функцию вставки символа/токена в поток
и удаления тоже

FeelUs Sep 17 2015 at 21:35

чет. я погорячился
для этого придется сделать совершенно другие буфера и итераторы

Hertz Sep 10 2015 at 15:41

Можно вот так, грамматика практически воплощается в синтаксисе языка, на котором пишется парсер. Испозуется short-circuiting бинарных булевых операторов.

read_expr(...) {
    return read_expr1(...) && read_expr2(...) && read_expr3(...);
}

mayorovp Sep 10 2015 at 15:45

С || будет уже далеко не так красиво.

FeelUs Sep 10 2015 at 20:39

Можно договориться в случае неудачи возвращать итератор в исходное положение,
и тогда будет

template<class it_t>
error_t read_expr_a(it_t & it,...) {
    it_t tmp = it;
    error_t err;
    if(err = read_expr1(it,...) && read_expr2(it,...) && read_expr3(it,...))
        return true;
    it = tmp;
    return err;
}
template<class it_t>
error_t read_expr_b(it_t & it,...) {
    return read_expr1(it,...) || read_expr2(it,...) || read_expr3(it,...);
}

mayorovp Sep 11 2015 at 06:22

Но теперь же && усложнилось…

FeelUs Oct 2 2015 at 19:14

Основная проблема в том, что short circuiting работает только с bool.
Но это решается лямбда-функциями и макросами, и теперь можно вызывать так:

return reifnot_E(it,read_expr1(it,...)&&E2F(read_expr2(it,...))&&E2F(read_expr2(it,...)))
||reifnot_E2F(it,read_expr4(it,...));

E2F превращает выражение в функцию без аргументов, а оператор && на основе левого аргумента уже решает, вызывать ее или нет.
Но все равно как-то неказисто да?

mayorovp Oct 2 2015 at 20:20

Если хочется красоты — надо переходить на нормальную алгебру парсеров. Как в Boost::Spirit, к примеру.

FeelUs Oct 5 2015 at 15:27

Вот, теперь вообще идеально:

return reifnot_E(it,read(it)>>expr1(...)>>expr2(...)>>expr2(...))
||reifnot_E2F(it,read_expr4(it,...));

Функция read(it) возвращает пару (итератор, ошибка), унаследованную от ошибки.
Для каждой функции read_something_xyz(it_t & it, A a, B b, C c) макрос DECLARE_SHORT_READING_N(something_xyz,something_xyz111) (N — кол-во аргументов без it) определет функцию something_xyz(A a, B b, C c), которая возвращает функциональный объект something_xyz111(it_t & it).
А operator>> берет пару-итератор-ошибка и функ. объект, по ошибке определяет стоит ли вызывать функ. объект, и если стоит, то его результат присваивается в ошибку, после чего возвращается пара-итератор-ошибка.

А если хочется что-то сделать с ошибкой, возвращаемой функ-объектом, то вот макрос на лямбда-функции

#define METHOD(it,fun,met)	[=](decltype(it) & it){	return fun(it).met;	}

mayorovp Oct 5 2015 at 19:58

Ну зачем же так сложно-то?..

return expr1(...) >> expr2(...) >> expr3(...) || expr4(...);

FeelUs Oct 9 2015 at 16:24

а кто в случае неудачи будет итератор на исходную позицию возвращать?

т.е. это не магия, которая все делает за тебя, а всего лишь укорачивание синтаксиса

base_parse_error err;
auto it1=it;
ifnot(err=read_expr1(it,...))
    goto met;
ifnot(err=err&&read_expr2(it,...)
    goto met:
ifnot(err=err&&read_expr3(it,...)
    goto met:
return err;//err==true
met:
it=it1;
return err||read_expr4(it,...);

большинство && и || с error-ами для base_parse_error бессмысленны, но если это error-ы, другого типа, например, сообщения об ошибках, то && и || становятся осмысленными

кстати это аналог

return reifnot_E(it,read(it)>>expr1(...)>>expr2(...)>>expr2(...))
||E2F(read_expr4(it,...));

— в конце reifnot можно не делать, его сделает вызывающая функция

mayorovp Oct 9 2015 at 16:52

Где вы в моем варианте вообще видите итератор? Итератор надо передавать потом, когда все комбинации уже закончатся…

DarkGenius Sep 10 2015 at 16:54

Какую хорошо литературу (помимо книги «Дракона») можно почитать по теории разработки анализаторов и трансляторов?

ilmirus Sep 10 2015 at 17:18

ИМХО, «Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages (Pragmatic Programmers)» будет даже лучше драгонбука.

KvanTTT Sep 10 2015 at 17:40

Мне вот эта очень помогла: The Definitive ANTLR 4 Reference, несмотря на то, что это больше про ANTLR.

datacompboy Sep 10 2015 at 18:39

Про классический вопрос, как правильно написать грамотную грамматику для случая
char * string;
var1 * var2;
уже задали?

FeelUs Sep 11 2015 at 12:10

Я бы стал делать так:
каждому до сих пор встретившемуся идентификатору сопоставляется, является ли он типом или нет
и дальше просто в лоб,
пытаемся прочитать объявление/определение (в простейшем случае оно должно начинаться с идентификатора-типа или typedef или ...)
если не получается (а мы проверили только первый идентификатор) — пытаемся прочитать выражение (а оно (в простейшем случае) состоит из идентификаторов-нетипов, литералов, и идентификаторов-типов в скобках (для приведения типа))
и если встретился необъявленный идентификатор — сообщаем об этом

к счастью такие конструкции недопустимы:

  typedef char var;
  int var, var1;
  var * var1;

FeelUs Sep 11 2015 at 12:17

и еще (в с++) выражение может содержать идентификатор-тип как конструктор, но тогда после него мы должны обнаружить '('

FeelUs Sep 24 2015 at 18:27

а вот пример, когда компилятор между классом и функцией предпочитает функцию:

#include <iostream>
using namespace std;
struct foo{
public:
  foo(int i){
    cout<<"type"<<endl;
  }
  int operator+(int){
    cout <<"foo+int"<<endl;
    return 2;
  }
};
int foo(int i){
  cout <<"fun"<<endl;
  return 1;
}
int main(){
  cout << (foo(5)+4) <<endl;
}

Show the best of all time