Применения: лексеры и парсеры

Вся теория наконец сходится в одном месте — внутри компилятора, где конечные автоматы и КС-грамматики работают бок о бок.

Компилятор — самое прямое применение курса: лексер — это конечный автомат, парсер — магазинный автомат по КС-грамматике.

Два этапа разбора кода

Когда компилятор читает исходный код, он проходит через две фазы, разделение которых — прямое следствие иерархии Хомского. Лексический анализ разбивает поток символов на токены (идентификаторы, числа, ключевые слова, операторы). Токены не вложены — их структура регулярна, поэтому лексер строится как конечный автомат (часто генерируется из регулярных выражений инструментами вроде lex/flex). Синтаксический анализ собирает токены в дерево по КС-грамматике языка — здесь нужна вложенность (выражения, блоки, скобки), поэтому работает магазинный автомат (парсеры LL/LR, генераторы yacc/bison/ANTLR).

исходный код:  if (x > 0) y = 1;

     ▼ ЛЕКСЕР (конечный автомат)
токены:  IF  (  ID:x  GT  NUM:0  )  ID:y  ASSIGN  NUM:1  ;

     ▼ ПАРСЕР (магазинный автомат, КС-грамматика)
              IfStmt
             /   |   \
        Cond   Then   …
        (x>0)  (y=1)

     ▼ дальше: семантика, генерация кода

Мини-лексер как конечный автомат

Напишем крошечный лексер для арифметики: числа, операторы, скобки. Это буквально конечный автомат, переключающий состояние по типу символа.

def tokenize(src):
    tokens, i = [], 0
    while i < len(src):
        ch = src[i]
        if ch.isspace():
            i += 1
        elif ch.isdigit():
            num = ""
            while i < len(src) and src[i].isdigit():
                num += src[i]; i += 1          # состояние "читаю число"
            tokens.append(("NUM", num))
        elif ch in "+-*/":
            tokens.append(("OP", ch)); i += 1
        elif ch in "()":
            tokens.append(("PAREN", ch)); i += 1
        else:
            tokens.append(("ERR", ch)); i += 1
    return tokens

for t in tokenize("12 + (34 * 5)"):
    print(t)

Вывод:

('NUM', '12')
('OP', '+')
('PAREN', '(')
('NUM', '34')
('OP', '*')
('NUM', '5')
('PAREN', ')')

Цикл с состояниями «читаю число / встретил оператор» — это и есть конечный автомат в действии. Заметьте: лексер не проверяет баланс скобок — это работа парсера со стеком.

Парсер как магазинный автомат

Теперь соберём из токенов значение выражения рекурсивным спуском — это прямая реализация КС-грамматики E→T(+T)*, T→F(*F)*, F→num|(E). Стек здесь — стек вызовов рекурсии.

def parse_eval(tokens):
    pos = 0
    def peek():
        return tokens[pos] if pos < len(tokens) else ("EOF", "")
    def expr():            # E -> T (+ T)*
        nonlocal pos
        val = term()
        while peek() == ("OP", "+"):
            pos += 1; val += term()
        return val
    def term():            # T -> F (* F)*
        nonlocal pos
        val = factor()
        while peek() == ("OP", "*"):
            pos += 1; val *= factor()
        return val
    def factor():          # F -> num | ( E )
        nonlocal pos
        tok = peek()
        if tok[0] == "NUM":
            pos += 1; return int(tok[1])
        if tok == ("PAREN", "("):
            pos += 1; v = expr(); pos += 1; return v   # съесть )
    return expr()

toks = [("NUM","2"),("OP","+"),("NUM","3"),("OP","*"),("NUM","4")]
print("2 + 3 * 4 =", parse_eval(toks))

Вывод:

2 + 3 * 4 = 14

Грамматика с уровнями E/T/F автоматически дала верный приоритет: умножение раньше сложения, 2+(3*4)=14. Рекурсия — это стек магазинного автомата, а уровни нетерминалов — устранение неоднозначности из пятого раздела.

Как работает под капотом

За пределами компиляторов теория автоматов вездесуща. Regex-движки (grep, RE2) компилируют шаблоны в ДКА/НКА — теорема Клини в коде. Верификация (model checking) кодирует систему и свойство автоматами и проверяет пересечение языков — замкнутость регулярных языков. Сетевые фильтры и лексеры протоколов — конечные автоматы. Проектирование языков опирается на КС-грамматики и классы LL/LR, чтобы парсер был эффективным и однозначным. Даже подсветка синтаксиса в редакторе — упрощённый лексер. Курс, начавшийся с абстрактных кружков и стрелок, оказался каркасом половины системного софта.

Частые ошибки

Парсить вложенное регуляркой. Скобки, теги, выражения — это КС, не регулярка; нужен парсер со стеком. Классическая ошибка — «распарсить HTML регэкспом».

Смешивать лексер и парсер. Разделение фаз не случайно: токены регулярны, синтаксис контекстно-свободен. Слитный код теряет ясность и эффективность.

Игнорировать приоритет в грамматике. Без уровней E/T/F парсер даст неверную группировку — приоритет кодируется структурой грамматики.

Итог

• Лексер — конечный автомат: разбивает код на токены (регулярная структура).
• Парсер — магазинный автомат по КС-грамматике: строит дерево из токенов (вложенная структура).
• Разделение лексер/парсер — прямое следствие границы регулярных и КС-языков.
• Теория работает повсюду: regex-движки (Клини), верификация (замкнутость), проектирование языков (LL/LR).