2.2.6 Нерегулярні множини

Деякі мови не можуть бути описані регулярними виразами. Для ілюстрації обмеженості описової потужності регулярних виразів наведемо приклади конструкцій мов програмування, які не можуть бути описані за допомогою регулярних виразів.

Регулярні вирази не можуть бути використані для опису збалансованих або вкладених конструкцій. Наприклад, з одного боку, множина всіх рядків зі збалансованих дужок не може бути описано регулярним виразом. З іншого боку, ця множина може бути описана за допомогою контекстно-вільної граматики.

Повторювані рядки також не можуть бути описані регулярними виразами. Множина

{wcw | w — рядок з а й b}

не може бути описано ні яким-небудь регулярним виразом, ні контекстно-вільною граматикою.

Регулярні вирази можуть використатися для опису тільки фіксованої (або невизначеної) кількості повторень даної конструкції. Два довільних числа не можуть порівнюватися в контексті регулярних виразів для з'ясування, рівні вони чи ні.

2.4. Розпізнавання токенів

У попередньому розділі ми розглянули проблему визначення (специфікації) токенів. У цьому розділі ми задамося питанням, як їх розпізнати. Тут як приклад використається мова, породжувана наступною граматикою.

Приклад 2.6

Розглянемо наступний фрагмент граматики:

stmt → if expr then stmt

| if expr then stmt else stmt

expr → term relop term

| term

term → id

| num

де нетермінали stmt, expr та term означають «оператор, «вираз» та «терм» відповідно, а термінали if, then, else, relop, id й num породжують множини рядків, що задають наступними регулярними визначеннями:

if → if

then → then

else → else

relop → < | <= | = | <> | > | >=

Id → letter (letter | digit)*

num → digit+ (. digit+)? (E(+ | -)? digit⁺)?

де letter й digit визначені так само, як і раніше.

Для цього фрагмента мови лексичний аналізатор буде розпізнавати ключові слова if, then, else, а також токени, позначені relop, id й num. Для простоти вважаємо, що ключові слова зарезервовані й, таким чином, не можуть використатися як ідентифікатори. Як й у прикладі 2.5, num представляє беззнакові цілі й дійсні числа Pascal.

Припустимо також, що лексеми розділені "порожнім простором", що складається з непустих послідовностей проміжків, символів табуляцій і нового рядка. Лексичний аналізатор має відкидати ці символи шляхом порівняння рядка з регулярним визначенням ws, наведеним нижче:

ws → delim+

delim → blank | tab | newline

Якщо знаходиться відповідність ws, лексичний аналізатор не повертає токен синтаксичному аналізатору. Замість цього відбувається пошук нового токену, що випливає за проміжками, і передача його синтаксичному аналізатору.

Регулярні вирази	ТОКЕН	атрибут-значення
ws	—	—
if	if	—
then	then	—
else	else	—
id	id	покажчик на запис у таблиці
num	num	покажчик на запис у таблиці
<	relop	LT
<=	relop	LE
=	relop	EQ
<>	relop	NE
>	relop	GT
>=	relop	GE

Рис. 2.10. Шаблони регулярних виразів для токенів

Наша мета — побудова лексичного аналізатора, що зможе виділяти із вхідного буферу лексему для наступного токену й, використовуючи таблицю трансляції на рис. 2.10, ви­давати пари, що складаються з токена й атрибута-значення. Атрибут-значення для операторів від­ношення визначається символічними константами LT,LE,EQ,NE, GT,GE.