Лексический анализатор должен сканировать и идентифицировать только конечный набор допустимых строк / токенов / лексем, которые принадлежат используемому языку. Он ищет шаблон, определенный правилами языка.
Регулярные выражения имеют возможность выражать конечные языки, определяя шаблон для конечных строк символов. Грамматика, определяемая регулярными выражениями, называется регулярной грамматикой . Язык, определяемый регулярной грамматикой, известен как обычный язык .
Регулярное выражение является важной нотацией для определения шаблонов. Каждый шаблон соответствует набору строк, поэтому регулярные выражения служат именами для набора строк. Языковые токены программирования могут быть описаны обычными языками. Спецификация регулярных выражений является примером рекурсивного определения. Обычные языки просты для понимания и имеют эффективную реализацию.
Существует ряд алгебраических законов, которым подчиняются регулярные выражения, которые можно использовать для манипулирования регулярными выражениями в эквивалентных формах.
операции
Различные операции над языками:
-
Союз двух языков L и M записывается как
LUM = {s | s находится в L или s находится в M}
-
Объединение двух языков L и M записывается как
LM = {st | s находится в L и t находится в M}
-
Закрытие клини языка L записывается как
L * = ноль или более вхождение языка L.
Союз двух языков L и M записывается как
LUM = {s | s находится в L или s находится в M}
Объединение двух языков L и M записывается как
LM = {st | s находится в L и t находится в M}
Закрытие клини языка L записывается как
L * = ноль или более вхождение языка L.
нотации
Если r и s являются регулярными выражениями, обозначающими языки L (r) и L (s), то
-
Союз : (r) | (s) — регулярное выражение, обозначающее L (r) UL (s)
-
Объединение : (r) (s) — это регулярное выражение, обозначающее L (r) L (s)
-
Закрытие Клини : (r) * — регулярное выражение, обозначающее (L (r)) *
-
(r) регулярное выражение, обозначающее L (r)
Союз : (r) | (s) — регулярное выражение, обозначающее L (r) UL (s)
Объединение : (r) (s) — это регулярное выражение, обозначающее L (r) L (s)
Закрытие Клини : (r) * — регулярное выражение, обозначающее (L (r)) *
(r) регулярное выражение, обозначающее L (r)
Приоритетность и ассоциативность
- *, конкатенация (.) и | (знак трубы) остаются ассоциативными
- * имеет высший приоритет
- Конкатенация (.) Имеет второй по значимости приоритет.
- | (знак трубы) имеет самый низкий приоритет из всех.
Представление действительных токенов языка в регулярном выражении
Если x является регулярным выражением, то:
-
х * означает ноль или более вхождения х.
то есть он может генерировать {e, x, xx, xxx, xxxx,…}
-
х + означает одно или несколько вхождений х.
то есть он может генерировать {x, xx, xxx, xxxx…} или xx *
-
Икс? означает не более одного вхождения х
т.е. он может генерировать либо {x}, либо {e}.
[az] — все строчные буквы английского языка.
[AZ] это все прописные буквы английского языка.
[0-9] — все натуральные цифры, используемые в математике.
х * означает ноль или более вхождения х.
то есть он может генерировать {e, x, xx, xxx, xxxx,…}
х + означает одно или несколько вхождений х.
то есть он может генерировать {x, xx, xxx, xxxx…} или xx *
Икс? означает не более одного вхождения х
т.е. он может генерировать либо {x}, либо {e}.
[az] — все строчные буквы английского языка.
[AZ] это все прописные буквы английского языка.
[0-9] — все натуральные цифры, используемые в математике.
Представление вхождения символов с помощью регулярных выражений
буква = [a — z] или [A — Z]
цифра = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 или [0-9]
знак = [+ | -]
Представление языковых токенов с помощью регулярных выражений
Десятичный = (знак) ? (цифра) +
Идентификатор = (буква) (буква | цифра) *
Единственная проблема, которая осталась с лексическим анализатором, заключается в том, как проверить правильность регулярного выражения, используемого при определении шаблонов ключевых слов языка. Хорошо принятым решением является использование конечных автоматов для проверки.