Приклад файлу з правилами виділення лексем для Flex

 

В даному прикладі розглядається побудова файлу з правилами виділення лексем для flex для імперативної мови програмування PL/0.

Розпізнаються наступні лексеми: '+', '-', '*', '/', '=', '(', ')', ',', ';', '.', ':=', '<', '<=', '<>', '>', '>='; числа: 0-9 {0-9}; ідентифікатори: a-zA-Z {a-zA-Z0-9} та ключові слова: begin, call, const, do, end, if, odd, procedure, then, var, while.

 

Файл lex.l матиме наступний вигляд:

 

%{

#include "y.tab.h"

%}

 

digit    [0-9]

letter   [a-zA-Z]

 

%%

"+"             { return PLUS;  }

"-"             { return MINUS; }

"*"             { return TIMES; }

"/"             { return SLASH; }

"("             { return LPAREN; }

")"             { return RPAREN; }

";"             { return SEMICOLON; }

","             { return COMMA; }

"."             { return PERIOD; }

":="            { return BECOMES; }

"="             { return EQL;   }

"<>"            { return NEQ;   }

"<"             { return LSS;   }

">"                  { return GTR;   }

"<="            { return LEQ;   }

">="            { return GEQ;   }

"begin"         { return BEGINSYM; }

"call"          { return CALLSYM; }

"const"         { return CONSTSYM;   }

"do"            { return DOSYM; }

"end"           { return ENDSYM; }

"if"            { return IFSYM; }

"odd"           { return ODDSYM; }

"procedure"     { return PROCSYM; }

"then"          { return THENSYM; }

"var"           { return VARSYM; }

"while"         { return WHILESYM; }

{letter}({letter}|{digit})* {

                  yylval.id = (char *)strdup(yytext);

                  return IDENT; }

{digit}+        { yylval.num = atoi(yytext);

                  return NUMBER; }

[ \t\n\r]       /* skip whitespace */

.               { printf("Unknown character [%c]\n",yytext[0]);

                  return UNKNOWN; }

%%

 

int yywrap(void){return 1;}

2. СИНТАКСИЧНИЙ АНАЛІЗ

 

2.1. Визначення синтаксичних правил мови програмування за допомогою формул Бекуса-Наура

 

Форма Бе́куса-Нау́ра (англ. Backus-Naur form, BNF) - це спосіб запису правил контекстно-вільної граматики, тобто це форма опису формальної мови.

Саме її типово використовують для запису правил мов програмування та протоколів комунікації. У 50-х роках минулого сторіччя Джон Бекус створив цю нотацію розробляючи мову ALGOL. На першому Всесвітньому Комп'ютерному Конгресі, що відбувся у Парижі 1959-го року він зробив доповідь на тему "Синтаксис та семантика пропонованої першої міжнародної алгебраїчної мови". Пізніше Наур Пітер спростив її та (за порадою Дональда Кнута) додав до назви своє ім'я.

Розши́рена фо́рма Бе́куса — На́ура (англ. extended Backus-Naur form, EBNF) є розширеною формою нотації Бекуса-Наура (BNF). Початково розроблена Ніклавсом Віртом, сьогодні вона існує в багатьох варіантах, перед усім у варіанті ISO-14977 [ Ошибка! Источник ссылки не найден. ].

Формули БНФ складаються з наступних мета символів:

· < – лівий обмежувач;

· > – правий обмежувач;

·::= – визначено як;

· | – або;

· “” — текстовий елемент (символ або група символів).

Розширені формули Бе́куса-Нау́ра використовують додаткові мета символи:

· [] – елемент у дужках входить або не входить (є необов’язковим);

· () – групування елементів у дужках;

· {} – нуль або більше повторень елементів розташованих у дужках;

· (* – початок блоку коментарів;

· *) – кінець блоку коментарів.

 

 Формули БНФ оперують термінальними і нетермінальними символами. Нетермінальні символи – це символи які введені для визначення “правил продукції”. Вони поміщаються в трикутні дужки: <цифра>. Натомість термінальні символи представляють лексеми або їх складові частини: 0,1,2,А,В,с,;,*,/,-,+.

Лексема - це мінімальна одиниця мови, що має значення. З лексемами також пов’язане поняття токен. Воно є загальнішим і відповідає групам лексем, наприклад, множина лексем, що відповідають умовним операторам, арифметичним операторам, тощо. 

Формули БНФ по суті є набором "правил продукції ", кожне з яких відповідає шаблону:

< Не термінальний символ >::= <вираз, що містить термінальні і не термінальні символи>

 

Формула виду:

А ::= { B }

позначає можливе повторення не термінального символу В нуль чи більше раз і є просто скороченим записом рекурсивного, по суті, правила:

A ::= <пусто> | AB

       При цьому слід чітко розуміти різницю між фігурними і квадратними дужками. Елементи між фігурними дужками можуть зустрічатися 0 або більше разів, так розділ оголошень змінних може не містити змінних (бути порожнім), або містити їх в великій кількості. Таким чином в цьому випадку слід застосувати фігурні дужки при описі синтаксичної конструкції <розділ оголошень >:

<розділ оголошень>::=Variables {<ідентифікатор>{,< ідентифікатор >}:<тип>;}

       Натомість при визначені синтаксичної конструкції <число> наявність знаку перед числом є необов’язковою, тому наявність знака в цій синтаксичній конструкції визначають використовуючи квадратні дужки:

<число>::=[+|-]<цифра>{<цифра>}

Увага!!! При описі синтаксису мови за допомогою БНФ слід уникати право і ліво рекурсивних синтаксичних конструкцій, які мають вигляд A::= zA і A::= Az відповідно.

 

Приклад визначення натуральних чисел за допомогою формул БНФ

 

<нуль>::= 0

<ненульова цифра>::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<цифра>::= <нуль> | <ненульова цифра>

<послідовність цифр>::= <нуль> | <ненульова цифра> | <цифра><послідовність цифр>

<натуральне число>::= <цифра> | <ненульова цифра><послідовність цифр>

 

В цьому прикладі 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – термінальні символи. Решта символів – не термінальні. Запис <ненульова цифра>::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 слід читати ненульова цифра визначена як 1 або 2 або 3 або 4 або 5 або 6 або 7 або 8 або 9 або 10. Запис <цифра>::= <нуль> | <ненульова цифра> слід читати цифра визначена як нуль або ненульова цифра.