Дизайн компилятора - регулярные выражения

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

Регулярные выражения имеют возможность выражать конечные языки, определяя шаблон для конечных строк символов. Грамматика, определяемая регулярными выражениями, называется регулярной грамматикой . Язык, определяемый регулярной грамматикой, известен как обычный язык .

Регулярное выражение является важной нотацией для определения шаблонов. Каждый шаблон соответствует набору строк, поэтому регулярные выражения служат именами для набора строк. Языковые токены программирования могут быть описаны обычными языками. Спецификация регулярных выражений является примером рекурсивного определения. Обычные языки просты для понимания и имеют эффективную реализацию.

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

операции

Различные операции над языками:

  • Объединение двух языков 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)

Приоритетность и ассоциативность

  • *, конкатенация (.) и | (знак трубы) остаются ассоциативными
  • * имеет высший приоритет
  • Конкатенация (.) Имеет второй по значимости приоритет.
  • | (знак трубы) имеет самый низкий приоритет из всех.

Представление действительных токенов языка в регулярном выражении

Если x является регулярным выражением, то:

  • х * означает ноль или более вхождения х.

    то есть он может генерировать {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]

знак = [+ | -]

Представление языковых токенов с помощью регулярных выражений

Десятичный = (знак) ? (цифра) +

Идентификатор = (буква) (буква | цифра) *

Единственная проблема, которая остается с лексическим анализатором, состоит в том, как проверить правильность регулярного выражения, используемого при указании шаблонов ключевых слов языка. Хорошо принятым решением является использование конечных автоматов для проверки.