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

[roman_kashitsyn]

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

[FeelUs]

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

[leshabirukov]

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

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

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

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

[mayorovp]

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

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

[Orient]

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

[leshabirukov]

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

[FeelUs]

да, оптимизировать придется самому:
можно так: expr ::= (expr '+' expr) | (expr '-' expr) | (expr '*' expr) | (expr '/' expr)
можно так: expr ::= expr ('+'|'-'|'*'|'/') expr
можно так: expr ::= expr ('+'expr |'-'expr |'*'expr |'/'expr )
(последние два варианта по производительности одинаковы, а различаются по кол-ву кода)

[KvanTTT]

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

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

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

[FeelUs]

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

[KvanTTT]

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

[FeelUs]

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

[FeelUs]

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

[Hertz]

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

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

[mayorovp]

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

[FeelUs]

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

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]

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

[FeelUs]

Основная проблема в том, что 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]

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

[FeelUs]

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

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]

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

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

[FeelUs]

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

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

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]

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

[DarkGenius]

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

[ilmirus]

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

[KvanTTT]

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

[datacompboy]

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

[FeelUs]

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

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

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

[FeelUs]

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

[FeelUs]

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

#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;
}