Сборка парсера (часть I)

Question

Я создаю свой собственный язык программирования на основе javascript (да, это безумие, но это только для изучения ... может быть? ). Что ж, я читаю о синтаксических анализаторах, и первый шаг - преобразование исходного кода в токены, например:

if(x > 5)
  return true;

Tokenizer to:

T_IF          "if"
T_LPAREN      "("
T_IDENTIFIER  "x"
T_GT          ">"
T_NUMBER      "5"
T_RPAREN      ")"
T_IDENTIFIER  "return"
T_TRUE        "true"
T_TERMINATOR  ";"

Я не знаю, верна ли моя логика для этого какое-то время. На моем парсере это даже лучше ( или нет? ) и перевести на него (ага, многомерный массив):

T_IF             "if"
  T_EXPRESSION     ...
    T_IDENTIFIER     "x"
    T_GT             ">"
    T_NUMBER         "5"
  T_CLOSURE        ...
    T_IDENTIFIER     "return"
    T_TRUE           "true"

У меня есть некоторые сомнения:

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

Ну, это так. Bye!

Answer 1

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

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

Просто чтобы дать вам более конкретныйВ качестве примера, основанного на вашем случае, я предполагаю, что вы можете написать две функции: accept(token) и expect(token), которые проверяют следующий токен в созданном вами потоке.Вы создадите функцию для каждого типа выражения или выражения в грамматике вашего языка.Вот 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) вашей программы, которое вы затем можете манипулировать (оптимизацией и анализом), вывод(сборник) или запустить (интерпретация).

Answer 2

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

• лексер (он же токенизатор)
• парсер (он же грамматика)

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

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

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

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 - абстрактное синтаксическое дерево), которая может выглядеть следующим образом:

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

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

Входные данные для структуры синтаксического анализатора грамматики обычно представляют собой формальную грамматику в некотором виде BNF .Ваша часть «если» может выглядеть так:

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ;

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

BinaryExpression: LeftOperand BinaryOperator RightOperand;

....

Это только для того, чтобы понять.Разбор языка реального мира, такого как Javascript , корректно - задача не из легких.Но смешно.

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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

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

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

Парсер получит информацию (он же "токен"Stream ») и сделайте так:

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

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