Построение парсера (часть I)

Ответ 1

Как правило, вы хотите отделить функции tokeniser (также называемого lexer) от других этапов вашего компилятора или интерпретатора. Причиной этого является базовая модульность: каждый проход потребляет один вид вещи (например, символы) и создает другой (например, токены).

Итак, вы превратили своих персонажей в токены. Теперь вы хотите преобразовать свой плоский список токенов в значимые вложенные выражения, и это то, что условно называется разбор. Для JavaScript-подобного языка вы должны изучить рекурсивный анализ спуска. Для разбора выражений с помощью инфиксных операторов с разными уровнями приоритета анализ Pratt очень полезен, и вы можете отказаться от обычного рекурсивного синтаксического анализа для особых случаев.

Чтобы дать вам более конкретный пример, основанный на вашем случае, Ill предположим, что вы можете написать две функции: accept(token) и expect(token), которые проверяют следующий токен в созданном вами потоке. Youll выполняет функцию для каждого типа выражения или выражения в грамматике вашего языка. Heres Pythonish псевдокод для функции statement(), например:

def statement():

  if accept("if"):
    x = expression()
    y = statement()
    return IfStatement(x, y)

  elif accept("return"):
    x = expression()
    return ReturnStatement(x)

  elif accept("{")
    xs = []
    while True:
      xs.append(statement())
      if not accept(";"):
        break
    expect("}")
    return Block(xs)

  else:
    error("Invalid statement!")

Это дает вам то, что называется абстрактным синтаксическим деревом (AST) вашей программы, которое вы затем можете манипулировать (оптимизация и анализ), вывод (компиляция) или запуск (интерпретация).

Ответ 2

Большинство наборов инструментов разбивают полный процесс на две отдельные части.

• lexer (aka. токенизатор)
• парсер (ака грамматика)

токенизатор будет разбивать входные данные на токены. Парсер будет работать только с токеном "поток" и строить структуру.

Ваш вопрос, похоже, сосредоточен на токенизаторе. Но ваше второе решение смешивает грамматический синтаксический анализатор и токенизатор в один шаг. Теоретически это также возможно, но для новичков гораздо проще сделать это так же, как и большинство других инструментов/фреймворков: отпустите отдельные шаги.

К вашему первому решению: я бы обозначил ваш пример следующим образом:

T_KEYWORD_IF   "if"
T_LPAREN       "("
T_IDENTIFIER   "x"
T_GT           ">"
T_LITARAL      "5"
T_RPAREN       ")"
T_KEYWORD_RET  "return"
T_KEYWORD_TRUE "true"
T_TERMINATOR   ";"

В большинстве языков ключевые слова не могут использоваться как имена методов, имена переменных и т.д. Это отражается уже на уровне токенизатора (T_KEYWORD_IF, T_KEYWORD_RET, T_KEYWORD_TRUE).

Следующий уровень возьмет этот поток и - с помощью формальной грамматики - построит некоторую структуру данных (часто называемую AST - Abstract Syntax Tree), которая может выглядеть так:

IfStatement:
    Expression:
        BinaryOperator:
            Operator:     T_GT
            LeftOperand: 
               IdentifierExpression:
                   "x"
            RightOperand:
                LiteralExpression
                    5
    IfBlock
        ReturnStatement
            ReturnExpression
                LiteralExpression
                    "true"
    ElseBlock (empty)

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

Вход для рамки анализатора грамматики обычно является формальной грамматикой в ​​виде BNF. Ваша "if" часть migh выглядит так:

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ;

Expression: LiteralExpression | BinaryExpression | IdentifierExpression | ... ;

BinaryExpression: LeftOperand BinaryOperator RightOperand;

....

Это только для того, чтобы получить идею. Анализ правильного языка, такого как Javascript, - это непростая задача. Но смешно.

Ответ 3

Мой путь лучше или хуже, чем оригинальный способ? Обратите внимание, что мой код будет считан и скомпилирован (переведен на другой язык, например PHP), вместо того, чтобы все время интерпретировать.

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

После я токенизатора, что мне нужно сделать точно? Я действительно потерялся на этом проходе!

После токенизации вам нужно разобрать его. Используйте некоторые хорошие рамки lexer/parser, такие как Boost.Spirit, или Coco, или что-то еще. Их сотни. Или вы можете реализовать свой собственный лексер, но для этого требуется время и ресурсы. Существует много способов анализа кода, я обычно полагаюсь на рекурсивный анализ спуска.

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

Есть ли хороший учебник, чтобы узнать, как я могу это сделать?

Как я уже говорил ранее, используйте инструменты для этого. Существует много хороших хорошо документированных рамок анализатора. Для получения дополнительной информации вы можете попросить некоторых людей, которые знают об этом. @DeadMG, на Lounge С++ строит язык программирования под названием "Широкий". Вы можете попросить его.

Ответ 4

Допустим, у меня есть это утверждение на языке программирования:

if (0 < 1) then
   print("Hello")

Лексер переведет это на:

keyword: if
num: 0
op: <
num: 1
keyword: then
keyword: print
string: "Hello"

Затем парсер возьмет информацию (также известную как "Token Stream") и сделает это:

if:
  expression:
    <:
      0, 1
then:
  print:
    "Hello"

Я не знаю, поможет это или нет, но я надеюсь, что это поможет.