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

В этой статье рассказывается, как писать синтаксические анализаторы с помощью этой небольшой библиотеки на с++.

Обычно, текст на машинном языке состоит из предложений, те — из подпредложений, а те, в свою очередь, из подподпредложений, и так вплоть до символов.

Например, элемент xml состоит из открывающего тега, содержимого и закрывающего тега. —> Открывающий тег состоит из '<', имени тега, возможно пустого списка атрибутов и '>'. —> Закрывающий тег состоит из '</', имени тега и '>'. —> Атрибут состоит из имени, знаков '=', '"', строки символов и снова '"'. —> Содержимое в свою очередь тоже может содержать элементы. —> И т.д. Таким образом, после разбора получается синтаксическое дерево.

Такие языки удобно описывать формой Бэкуса-Наура (БНФ), где каждый нетерминал соответствует некоторому предложению языка. Когда мы пишем программы, мы обычно разбиваем их на функции и подфункции, и раз мы собрались писать синтаксический анализатор, пусть каждому нетерминалу БНФ соответствует одна функция нашего анализатора, и пусть каждая такая функция:

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

Например для БНФ вида expr ::= expr1 expr2 expr3 будем писать такую функцию:

bool read_expr(char *& p, ....){
	if(!read_expr1(p, ....))
		return false;
	//функция read_expr1() оставляет p там, где завершился разбор expr1
	//так что никаких манипуляций с p в данном месте не требуется
	if(!read_expr2(p, ....))
		return false;
	if(!read_expr3(p, ....))
		return false;
	/*обработку возвращаемых значений добавить по вкусу*/
	return true;
}

А для предложения БНФ вида expr ::= expr1 | expr2 | expr3 — функцию:

bool read_expr(const char *& p, ....){
	const char * l = p;
	if(read_expr1(p, ....))
		return true;
	//p может указывать на точку, где произошла ошибка при разборе expr1
	p = l;
	if(read_expr2(p, ....))
		return true;
	p = l;
	if(read_expr3(p, ....))
		return true;
	return false;
	/*обработку возвращаемых значений добавить по вкусу*/
}

(Кажется это называется синтаксический анализ с возвратами)

Не всякий текст, удовлетворяющий БНФ нам может подходить. Например элемент языка xml может описываться так: element ::= '<'identifier'>'some_data'</'identifier'>' , но это предложение будет действительно элементом, только если идентификаторы совпадают. Такие (или аналогичные) проверки можно легко добавлять в функции разбора.

Терминальные функции могут выглядеть например так:

bool read_fix_char(const char *& it, char c){
	if(!*it) 	return false;//конец строки 
	if(*it!=c)    	return false;//не тот символ
			//в случае неудачи указатель останется на месте
	it++;		//в случае удачи перейдет к следующему символу
	return true;
}
bool read_fix_str(const char * & it, const ch_t * s){
	while(*it)//пока не конец строки
		if(!*s)
			return true;
		else if(*it!=*s)
			return false;
			//в случае неудачи указатель будет указывать на отличающийся символ
		else
			it++, s++;
	if(!*s) return true;
	return false;//конец строки оказался раньше ожидаемого
}

Пока что мы делали синтаксический анализ строки. Но заметим, что для всех типов вышеперечисленных функций достаточно forward итераторов.

forward stream


Зададимся целью создать класс-поток, предоставляющий forward итераторы, и хранящий в памяти файл не целиком а небольшими кусочками. Тогда, если сделать функции разбора шаблонными, то их можно будет использовать и со строкамии, и с потоками. (Что и сделано в «base_parse.h» для терминальных (и около того )функций.) Но сначала внесем некоторые разъяснения в идеологию unix «все есть файл»: Бывают файлы располагающиеся на диске — их можно читать несколько раз и с любой позиции (назовем их random-access файлами ). А бывают потоки, перенаправленные из других программ, идущие по сети или от пользователя с клавиатуры (назовем их forward потоками). Такие потоки можно читать только за один проход. (fixme) По этому, что бы можно было работать и с тем и с другим, зададимся целью создать класс-поток, читающий файл за один проход, предоставляющий forward итераторы, и хранящий в памяти файл не целиком а небольшими кусочками.

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



Forward итераторы отличаются от input итераторов тем, что их можно копировать. Для потока с forward итераторами решением будет список буферов. Как только какой-нибудь итератор выходит за пределы самого правого буфера, в список добавляется новый буфер, и заполняется непосредственно из файла блоком данных. Но постепенно так в память загрузится весь файл, а мы этого не хотим. Сделаем так, чтоб удалялись все буфера, находящиеся левее буфера на котором находится самый левый (отстающий) итератор. Но мы не будем каждому буферу сопоставлять список итераторов, находящихся на нем, а будем сопоставлять всего лишь их количество (подсчет итераторов). Как только какой-нибудь буфер узнает, что на нем осталось 0 итераторов и что он самый левый, тогда удаляется он и все соседние буфера правее него, на которых тоже 0 итераторов.



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

Когда итератор доходит до границы буфера, он смотрит, есть ли в списке буферов следующий, если его нет — загружает его, на предыдущем буфере уменьшает счетчик итераторов, а на следующем увеличивает. Если на предыдущем буфере осталось 0 итераторов — он удаляется. Если итератор дошел до конца файла — он только отвязывается от предыдущего буфера и переходит в состояние «конец файла». При копировании итератора — увеличивается счетчик итераторов на буфере на котором он находится, а при вызове деструктора итератора — счетчик уменьшается, и, опять же, если на буфере осталось 0 итераторов, то он и соседние справа буфера, на которых тоже 0 итераторов, — удаляются. Детали реализации смотри в «forward_stream.h».

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

В качестве бонуса, есть различные типы буферов: простые (basic_simple_buffer), с вычислением строки-столбца по итератору (basic_adressed_buffer), планируется сделать буфер, осуществляющий перекодировку между различными кодировками. В связи с чем поток параметризуется типом буфера.

atend()


Конец сишной строки определяется нулевым символом. Это означает, что пока мы движемся по строке, чтобы обнаружить ее конец, нам надо не сравнивать указатель с другим указателем (как это традиционно делается в STL), а надо проверять значение, указываемое нашим указателем. С файлами примерно такая же ситуация: при посимвольном вводе char-ов мы получаем int-ы, и т.к. у них диапозон значений больше, мы опять же тестируем каждый символ на равенство EOF. Масла в огонь добавляет тот факт, что для forward потоков, поступающих в реальном времени, положение конца файла заранее неизвестно.

Эту информацию можно обобщить, сделав функцию atend(it), которая для указателей по строке будет выглядеть так:

bool atend(const char * p)
{ return !*p; }

А для итераторов по потоку она будет возвращать true, когда итератор указывает на конец файла.

strin


Для интерактивного взаимодействия с пользователем (через stdin) блочная буферизация не подходит, т.к. в блоке чаще всего помещается несколько строк, и после ввода одной строки программа продолжает ожидать ввода от пользователя, т.к. блок все еще не заполнен. Для этого необходима строковая буферизация, когда буфер заполняется символами вплоть до символа перевода строки. В этой библиотеке можно выбрать тип буферизации при помощи выбора типа файла, от которого инициализируется поток (basic_block_file_on_FILE или string_file_on_FILE).

strin — внутренний итератор потока над stdin'ом со строковой буферизацией.
Для неинтерактивных файлов при создании потока создается итератор, указывающий на первый символ, а значит загружается первый буфер. Для strin'а это не допустимо, т.к. программист может захотеть что-то выполнить или вывести на экран до того как программма перейдет в режим ожидания ввода строки.

По этому строковые файлы при заполнении первого буфера выдают фиктивную строку "\n". Для ее прочтения существует функция start_read_line(it), после выполнения которой программа переходит в режим ожидания ввода строки после чего можно произвести синтаксический анализ этой строки, не выводя при этом итераторы за пределы следующего символа '\n'.

Поле анализа прграммист может захотеть опять что-то вывести на экран, и если после этого ему опять понадобятся данные от пользователя, то перед их получением снова следует вызвать start_read_line(strin).

Т.о. получается цикл:
while(true){
	cout << "приглашение" <<endl;
	start_read_line(strin); //явный запрос ввести строку
	analys(strin);
}

Конечно это костыль, и можно было бы сделать итераторы, которые требуют загрузки буфера только при разыменовании, но это привело бы к дополнительным проверкам при разименовании и просто усложнению всей системы…

Базовые функции парсинга


Что бы пользователю не приходилось каждый раз заново писать терминальные функции, они в «base_parse.h» уже реализованы. Сейчас они реализованы (кроме обработки плавающих чисел) в общем виде, в дальнейшам планируется специализировать их с использованием строковых функций (таких как strcmp, strstr, strchr, strspn, strcspn) для указателей по строкам и для итераторов по потокам. Также они позволяют пользователю почти не думать о конце файла, и просто задают стиль кода.

Ниже представлена краткая сводка базовых функций парсинга, возвращаемые значиния и статистика их использования при реализации двух тестовых парсеров.

size_t      n
ch_t        c
ch_t *      s
func_obj    bool is(c)  //наподобие bool isspace(c)
span        spn  //см выше
bispan      bspn  //см выше
func_obj    err pf(it*) //наподобие int read_spc(it*)
func_obj    err pf(it*, rez*)

len - кол-во символов, добавлненных в *pstr
.                                                               возвращаемое значение в случае  реализованность 
название                    аргументы           рег.выр.        если EOF    если не EOF     статистика использования
int read_until_eof          (it&)               .*$             0           0               1   OK
int read_until_eof          (it&,    pstr*)     .*$             len         len                 OK
int read_fix_length         (it&, n)            .{n}            -1          0                   OK
int read_fix_length         (it&, n, pstr*)     .{n}            -(1+len)    0               2   OK

int read_fix_str            (it&, s)            str             -(1+len)    0 или (1+len)   9   OK
int read_fix_char           (it&, c)            c               -1          0 или 1         11  OK
int read_charclass          (it&, is)           [ ]             -1          0 или 1             OK
int read_charclass          (it&, spn)          [ ]             -1          0 или 1             OK
int read_charclass          (it&, bspn)         [ ]             -1          0 или 1             OK
int read_charclass_s        (it&, is, pstr*)    [ ]             -1          0 или 1             OK
int read_charclass_s        (it&, spn, pstr*)   [ ]             -1          0 или 1         1   OK
int read_charclass_s        (it&, bspn, pstr*)  [ ]             -1          0 или 1         5   OK
int read_charclass_c        (it&, is, ch*)      [ ]             -1          0 или 1             OK
int read_charclass_c        (it&, spn, ch*)     [ ]             -1          0 или 1         1   OK
int read_charclass_c        (it&, bspn, ch*)    [ ]             -1          0 или 1             OK
int read_c                  (it&, ch*)          .               -1          0               5   OK

int read_while_charclass    (it&, is)           [ ]*            -(1+len)    len                 OK
int read_while_charclass    (it&, spn)          [ ]*            -(1+len)    len             2   OK
int read_while_charclass    (it&, bspn)         [ ]*            -(1+len)    len                 OK
int read_while_charclass    (it&, is, pstr*)    [ ]*            -(1+len)    len                 OK
int read_while_charclass    (it&, spn, pstr*)   [ ]*            -(1+len)    len                 OK
int read_while_charclass    (it&, bspn, pstr*)  [ ]*            -(1+len)    len             1   OK
int read_until_charclass    (it&, is)           .*[ ]<-         -(1+len)    len                 OK
int read_until_charclass    (it&, spn)          .*[ ]<-         -(1+len)    len             1   OK
int read_until_charclass    (it&, bspn)         .*[ ]<-         -(1+len)    len                 OK
int read_until_charclass    (it&, is, pstr*)    .*[ ]<-         -(1+len)    len                 OK
int read_until_charclass    (it&, spn, pstr*)   .*[ ]<-         -(1+len)    len             2   OK
int read_until_charclass    (it&, bspn, pstr*)  .*[ ]<-         -(1+len)    len                 OK
int read_until_char         (it&, c)            .*c             -(1+len)    len                 OK
int read_until_char         (it&, c, pstr*)     .*c             -(1+len)    len                 OK
<- - говорит о том, что что после прочтения последнего символа итератор стоит не после него а на нем

int read_until_str          (it&, s)            .*str           -(1+len)    len             2   OK
int read_until_str          (it&, s, pstr*)     .*str           -(1+len)    len             1   OK
int read_until_pattern      (it&, pf)           .*( )           -(1+len)    len                 OK
int read_until_pattern      (it&, pf, rez*)     .*( )           -(1+len)    len                 OK
int read_until_pattern_s    (it&, pf, pstr*)    .*( )           -(1+len)    len                 OK
int read_until_pattern_s    (it&, pf, pstr*, rez*)  .*( )       -(1+len)    len                 OK

ch_t        c
ch_t *      s
func_obj    bool is(c)  //наподобие bool isspace(c)
span        spn  //см выше
bispan      bspn  //см выше
func_obj    err pf(it*) //наподобие int read_spc(it*)
func_obj    err pf(it*, rez*)

len - кол-во символов, добавлненных в *pstr
.                                                               возвращаемое значение в случае  реализованность 
название                    аргументы           рег.выр.        если EOF    если не EOF     статистика использования
int read_line               (it&, s)            .*[\r\n]<-      -1 или len  len                 OK
int read_line               (it&)               .*[\r\n]<-      -1 или len  len             1   OK
int start_read_line         (it&)               .*(\n|\r\n?)    -1          0 или 1         8   OK
<- - говорит о том, что что после прочтения последнего символа итератор стоит не после него а на нем

int read_spc                (it&)               [:space:]       -(1+len)    len                 OK
int read_spcs               (it&)               [:space:]*      -(1+len)    len             5   OK
int read_s_fix_str          (it&, s)            [:space:]*str   -(1+len)    0 или len       1   OK
int read_s_fix_char         (it&, c)            [:space:]*c     -1          0 или 1         8   OK
int read_s_charclass        (it&, is)           [:space:][ ]    -1          0 или 1             OK
int read_s_charclass_s      (it&, is, pstr*)    [:space:][ ]    -1          0 или 1             OK
int read_s_charclass_c      (it&, is, pc*)      [:space:][ ]    -1          0 или 1         2   OK
int read_bln                (it&)               [:blank:]       -(1+len)    len                 OK
int read_blns               (it&)               [:blank:]*      -(1+len)    len             1   OK
int read_b_fix_str          (it&, s)            [:blank:]*str   -(1+len)    0 или len           OK
int read_b_fix_char         (it&, c)            [:blank:]*c     -1          0 или 1             OK
int read_b_charclass        (it&, is)           [:blank:][ ]    -1          0 или 1             OK
int read_b_charclass_s      (it&, is, pstr*)    [:blank:][ ]    -1          0 или 1             OK
int read_b_charclass_c      (it&, is, pc*)      [:blank:][ ]    -1          0 или 1             OK

int_t может быть : long, long long, unsigned long, unsigned long long - для специализаций
[:digit:]   ::= [0-"$(($ss-1))"]
sign        ::= ('+'|'-')
int         ::= spcs[sign]spcs[:digit:]+
.                                                                                                                   специализация для
.                                                                                                                   [w]char char16/32   stream_string     
.                                                                           возвращаемое значение в случае  реализованность     
название                аргументы               рег.выр.                    неудача переполнение    статистика использования
int read_digit          (it&, int ss, int_t*)   [:digit:]                   1       -1(EOF)         1       OK
int read_uint           (it&, int ss, int_t*)   [:digit:]+                  1       -1              1       OK
int read_sign_uint      (it&, int ss, int_t*)   [sign][:digit:]+            1       -1                      OK
int read_sign_s_uint    (it&, int ss, int_t*)   [sign]spcs[:digit:]+        1       -1              1       OK
int read_int            (it&, int ss, int_t*)   spcs[sign]spcs[:digit:]+    1       -1              1       OK      OK
int read_dec            (it&, int_t*)           int#[:digit:]=[0-9]         1       -1              1       OK      OK
int read_hex            (it&, int_t*)           int#[:digit:]=[:xdigit:]    1       -1                      OK      OK
int read_oct            (it&, int_t*)           int#[:digit:]=[0-7]         1       -1                      OK      OK
int read_bin            (it&, int_t*)           int#[:digit:]=[01]          1       -1                      OK      OK

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

#define r_if(expr)             if((expr)==0)
#define r_while(expr)       while((expr)==0)
#define r_ifnot(expr)           if(expr)
#define r_whilenot(expr)     while(expr)
/*
r_ifnot(err=read_smth(it))//если что-то не прочитано
    return err;
*/
//следующие используются совместно с read_while_sm и read_until
#define rm_if(expr)            if((expr)>=0)     //типа рег. выр.  '.*' * - multiple -> m
#define rm_while(expr)      while((expr)>=0)
#define rm_ifnot(expr)         if((expr)<0)
#define rm_whilenot(expr)   while((expr)<0)
#define rp_if(expr)            if((expr)>0)      //типа рег. выр.  '.+' + - plus -> p
#define rp_while(expr)      while((expr)>0)
#define rp_ifnot(expr)         if((expr)<=0)
#define rp_whilenot(expr)   while((expr)<=0)
/*
rm_if(read_until_char(it,'\n'))//если прочитано 0 или более символов и символ \n
rp_if(read_until_char(it,'\n'))//если прочитано 1 или более символов и символ \n
*/

Хотя вполне возможно сделать какой-нибудь класс, хранящий эту информацию и преобразуемый к bool соответствующим образом.

Вообще я противник неконстантных ссылок, и считаю, что аргументы, которые функция должна изменить, должны передаваться в нее по указателю а не по ссылке, что бы при вызове это было видно, но всвязи с тем, что операторы для указателей на что бы то ни было перегружать нельзя, специально для совместимости с operator>>() (парочка таких определена в «strin.h») я итераторы везде передаю по ссылке (а возвращаемые значения по указателю).

На данный момент имеется два примера использования этих функций: calc.cpp и winreg.cpp.



Таким образом для написания парсера не требуется умения обращаться с другими программами генерации парсеров. Каждый нетерминал БНФ взаимнооднозначно переводится в функцию, которая, конечно, громоздковата по сравнению с описанием в БНФ (это можно в дальнейшем исправить, сделав функцию, делающую разбор по регулярному выражению, аналогично как в <boost/xpressive>), но зато в нее можно добавить любую проверку и обработку данных. Все это можно делать как со строками, так и с потоками в одинаковой форме. Поток ввода по умолчанию готов к вводу по умолчанию, а операторы >>, аналогичные таким же из стандартной библиотеки, дают возможность использовать эту библиотеку вместо стандартной библиотеки ввода.

Как с помощью forward_stream делать токенезацию, я попробую рассказать и показать в следующей статье.
Поделиться публикацией
Комментарии 29
    +4
    Я правильно понимаю, что вы описали Recursive Descent Parser?
      0
      да
      стандартная библиотека си (да и с++ наверно) дает возможность реализовывать LL(1) грамматики (при помощи ungetc())
      а forward_stream дает возможность реализовывать LL(*) грамматики
      0
      Вот есть грамматика:
      ...
      expr ::= expr '+' expr
      expr ::= expr '-' expr
      expr ::= expr '*' expr
      expr ::= expr '/' expr
      

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

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

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

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

            Я конечно понимаю, что иногда нужно создавать собственный велосипед. Но, честно говоря, лучше бы вы все же использовали ANTLR для описания грамматики и дорабатывали рантайм под C++: antlr4-cpp. У него куча грамматик еще реализована, причем в более лаконичном формате EBNF.
              0
              Я никогда не понимал, какое поведение у стандартной библиотеки при неудачном вводе
              по этому это скорее моя стандартная библиотека ввода с возможностью на ней писать парсеры с возможностью неограниченного просмотра вперед (но с ручной оптимизацией грамматик),
              чем средство специально для написания парсеров.
                0
                Нужно изучать инструмент, который используешь. В ANTLR система обработки ошибок достаточно сильно продумана, например при отсутствующем токене, он может «достроиться» сам, чтобы в данном участке кода парсер детектировал только одну ошибку, а не множество.
                В книге по ANTLR есть отдельная глава, посвященная обработке ошибок.
                  0
                  о, кстати можно добавить функцию вставки символа/токена в поток
                  и удаления тоже
                    0
                    чет. я погорячился
                    для этого придется сделать совершенно другие буфера и итераторы
              0
              Можно вот так, грамматика практически воплощается в синтаксисе языка, на котором пишется парсер. Испозуется short-circuiting бинарных булевых операторов.
              read_expr(...) {
                  return read_expr1(...) && read_expr2(...) && read_expr3(...);
              }
              
                0
                С || будет уже далеко не так красиво.
                  0
                  Можно договориться в случае неудачи возвращать итератор в исходное положение,
                  и тогда будет
                  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,...);
                  }
                  
                    0
                    Но теперь же && усложнилось…
                      0
                      Основная проблема в том, что 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 превращает выражение в функцию без аргументов, а оператор && на основе левого аргумента уже решает, вызывать ее или нет.
                      Но все равно как-то неказисто да?
                        0
                        Если хочется красоты — надо переходить на нормальную алгебру парсеров. Как в Boost::Spirit, к примеру.
                          0
                          Вот, теперь вообще идеально:
                          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;	}
                          
                            0
                            Ну зачем же так сложно-то?..
                            return expr1(...) >> expr2(...) >> expr3(...) || expr4(...);
                            
                              0
                              а кто в случае неудачи будет итератор на исходную позицию возвращать?

                              т.е. это не магия, которая все делает за тебя, а всего лишь укорачивание синтаксиса
                              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 можно не делать, его сделает вызывающая функция
                                0
                                Где вы в моем варианте вообще видите итератор? Итератор надо передавать потом, когда все комбинации уже закончатся…
                0
                Какую хорошо литературу (помимо книги «Дракона») можно почитать по теории разработки анализаторов и трансляторов?
                  0
                  ИМХО, «Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages (Pragmatic Programmers)» будет даже лучше драгонбука.
                    0
                    Мне вот эта очень помогла: The Definitive ANTLR 4 Reference, несмотря на то, что это больше про ANTLR.
                    +3
                    Про классический вопрос, как правильно написать грамотную грамматику для случая
                    char * string;
                    var1 * var2;
                    уже задали?
                      0
                      Я бы стал делать так:
                      каждому до сих пор встретившемуся идентификатору сопоставляется, является ли он типом или нет
                      и дальше просто в лоб,
                      пытаемся прочитать объявление/определение (в простейшем случае оно должно начинаться с идентификатора-типа или typedef или ...)
                      если не получается (а мы проверили только первый идентификатор) — пытаемся прочитать выражение (а оно (в простейшем случае) состоит из идентификаторов-нетипов, литералов, и идентификаторов-типов в скобках (для приведения типа))
                      и если встретился необъявленный идентификатор — сообщаем об этом

                      к счастью такие конструкции недопустимы:
                        typedef char var;
                        int var, var1;
                        var * var1;
                      
                        0
                        и еще (в с++) выражение может содержать идентификатор-тип как конструктор, но тогда после него мы должны обнаружить '('
                          0
                          а вот пример, когда компилятор между классом и функцией предпочитает функцию:
                          #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;
                          }
                          

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое