ru.linux

 
 - RU.LINUX ---------------------------------------------------------------------
 From : Alexander Lubyagin                   2:5056/16.70   08 Jan 2005  10:19:38
 To : Nikolay Popov
 Subject : bison, лексический и синтаксический анализ
 -------------------------------------------------------------------------------- 
 

 07 Jan 05 23:35, you wrote to all:
 
 NP> Кто нибудь работал с сабжем? Мне нужно парсить конфиг вида string
 NP> value; а также ввод пользователя с telnet-сессии в С программе,
 NP> [skipped]
 
 Hу, давай разберемся с проблемой вместе.
 
 Генератор синтаксических анализаторов, совместимый с YACC
 для Bison версии 1.35, 25 февраля 2002 года
 Чарльз Доннелли, Ричард Столлмен
 http://www.gnu.org.ru/bison/bison_toc.html
 
 Коротко:
 Bison предназначен для разбора языков, описываемых контекстно-свободными
 грамматиками. Одна из форм представления КС-грамматик - форма Бэкуса-
 Hауэра (была разработана для описания языка Algol 60).
 
 "3.1.1. Лексический анализатор rpcalc.
  Задачей лексического анализатора является низкоуровневый разбор -
  преобразование литер или последовательностей литер входного текста
  в лексемы. Анализатор Bison получает эти лексемы, вызывая лексический
  анализатор. См. раздел 5.2. Функция лексического анализатора yylex"
 
 Для разбора текстов по произвольным грамматикам и для автоматического
 создания лексических анализаторов на C/C++ можно использовать flex
 - fast lexical analyzer generator.
 http://www.citforum.ru/operating_systems/manpages/FLEX.1.html
 Синтаксический же анализ вести средствами bison (yacc).
 
 Каким же образом пристыковать flex к bison ?
 1. Вначале написать лексический анализатор (программу
    для лексического анализа) на flex.
    Оттранслировать ее на C/C++: flex -o${NAME}.c ${NAME}.l
 2. Затем описать грамматику языка с помощью синтаксических правил
    для bison и оттранслировать синтаксический анализатор на C/C++:
    bison -o${NAME}.c ${NAME}.y
 
 Получили два исходника на C/C++
 Второй из них содержит неразрешенные ссылки (ссылки на неопределенные
 функции), находящиеся в первом исходнике, например: yylex, yyerror.
 Первый содержит также определение функции main.
 
 Более подробную информацию об этих файлах получаем командой:
 cproto -s -v -f 2 ${NAME} > ${NAME}.cproto и командой:
 ctags -h.h.c -x --if0=yes -u \
 --format=2 \
 --c-types=cdefgmnpstuvx \
 --file-scope=yes \
 --language-force=c \
 --excmd=mixed \
 --verbose=yes ${NAME} > ${NAME}.ctags
 Для C++ получение прототипов аналогично.
 
 Тип возвращаемой лексическим анализатором лексемы
 определяется целым числом, соответствующим данному терму (токену,
 token - см. Чарльз Доннелли, Ричард Столлмен)
 
 Если синтаксис файла - элементарный, то можно ограничиться средствами flex.
 Hапример, вот программа на flex для проверки парности скобок:
 
 -------
     int nm = 0;
     int np = 0;
     int ne = 0;
 
     #define NX " "  // end of term
 
 %%
 -[0-9]+ { printf ("#"NX); }
 [0-9]+  { printf ("#"NX); }
 "+"     { printf ("*"NX); }
 "-"     { printf ("*"NX); }
 "("     { np = np + 1; printf ("{"NX); }
 ")"     { nm = nm + 1; printf ("}"NX);
           if (nm > np) ne = ne+1;
         }
 "\r"    { printf (""NX); }
 "\n"    { printf (""NX); }
 <<EOF>> { printf (""NX); return 0; }
 %%
 
 int main () {
     yylex();
     printf ("\n");
     if (nm == np) printf ("Passed\n");
     else printf ("Failed: %d errors\n",(ne==0?1:ne));
     return 0;
 }
 -------
 
 flex -ocalc.c calc.l
 gcc -O3 -ocalc calc.c -ll
 chmod u+x calc
 echo "2+(2+2)" | ./calc
 # * { # * # }
 Passed
 echo "2+(2+2" | ./calc
 # * { # * #
 Failed: 1 errors
 echo "2+(2+2)))" | ./calc
 # * { # * # } } }
 Failed: 2 errors
 P.S.
 
 Можешь посмотреть также книгу Креншоу, "Давайте создадим компилятор!"
 Глава 7, Лексический анализ (Объединение сканера и парсера). Это поможет
 понять англоязычную терминологию.
 
 Hаша терминология по теории лексического и синтаксического анализа
 грамотно изложена в книге "Формальные грамматики и языки. Элементы
 теории трансляции" (Волкова И.А., Руденко Т.В. - они вели у нас
 два семестра семинар по языкам C/C++ и теории трансляции)
 
 Еще, afaik, работа yacc/lex подробно описана в кнгие Кернигана
 и Пайка по ОС UNIX.
 
 --- GoldED+/LNX Debian
  * Origin: KOSC/Kirov Open Source Community (2:5056/16.70)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    bison   Nikolay Popov   08 Jan 2005 00:35:20   bison, лексический и синтаксический анализ   Alexander Lubyagin   08 Jan 2005 10:19:38