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

Я делаю свой собственный язык программирования на основе 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"

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

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

Ну, это так. До свидания!

 David Rodrigues26 февр. 2012 г., 12:33
@ IntermediateHacker Хаха ... Да,псих часть в том, что это очень сложно для одного человека сделать это. Но учиться - это очень хорошая вещь, правда. Для профессионального использования я предполагаю, что нужна команда, поэтому сумасшедший делает это один. :п
 stryba26 февр. 2012 г., 12:33
Вы пробовали Книгу Дракона? По сути, то, что вы называете первым, это этап лексера, за которым следует этап синтаксического синтаксического анализа -> в идеале, вывод некоторого вида AST (абстрактного синтаксического дерева), который затем можно семантически анализировать (анализировать) или преобразовывать в целевой язык.
 ApprenticeHacker26 февр. 2012 г., 12:19
Эй, создание языка программирования не сумасшедший. Многие люди здесь делают то же самое.

Ответы на вопрос(3)

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

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

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

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

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

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

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

Решение Вопроса

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

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

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

отдельный части

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

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

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

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

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правильно это не простая задача. Но смешно

Ваш ответ на вопрос