Привет от другого читателя siiiiiiide (здесь звучит Adele), приятно видеть вас снова во втором эпизоде этой серии, где мы освещаем основные аспекты теории компиляторов, создавая интерпретатор выражений lisp в Elixir. Если вы все еще не читаете первую часть или просто хотите ознакомиться с концепцией, нажмите здесь!
Давайте начнем
Что такое синтаксический анализ?
Подобно реальному языку, например английскому, расположение слов должно соответствовать фразовому порядку, например:
Кошка и собака становятся друзьями.
Это имеет смысл, потому что я прямо указываю, что собака и кошка являются субъектами, а после этого я выражаю их действия, заключающиеся в том, чтобы подружиться, но если предложение было написано так:
Кошка друзей и ставшая собакой .
Это не имеет никакого смысла, потому что правильный порядок, ожидаемый языком, полностью испорчен.
И то же самое можно увидеть в нашей программе, например, если у нас есть такое выражение:
)(6(+(*) 3
Эта программа лексически корректна, но синтаксически она не следует порядку и не имеет смысла, поэтому для того, чтобы сделать наши программы корректными, нам нужна грамматика свободного контекста, а после нее мы должны построить дерево разбора.
Наша свободная контекстная грамматика для наших лисп-выражений будет следующей:
O -› (
C -› )
N -> 0..9|ORNNC
R -> {+, -, *, /}
EXP -> ORNNC
А наша программа:«(+ 5 5)» сгенерирует следующее дерево синтаксического анализа:
EXP / / | \ \ O R N N C | | | | | ( + 5 5 )
Теперь, когда мы получили теорию, давайте перейдем к Эликсиру и реализуем наш синтаксический анализатор.
Давайте создадим файл нашего модуля:
lisp_eval/lib/lisp_eval/sintatic_analysis.ex
defmodule SyntaticAnalysis do end
И после этого давайте создадим наше первое правило: сбалансированная скобка
defmodule SyntaticAnalysis do
def syntatic_analysis([{:open_paren, _} | tail], parens, pt), do: operator tail, parens+1, pt
def syntatic_analysis([{:close_paren, _} | tail], parens, pt), do: operator tail, parens-1, pt
def syntatic_analysis([], 0, pt), do: pt
def syntatic_analysis([], _, _), do: raise "Open close parens not equally balanced."
end
Функция в основном создает правило, что если наша программа:
Начинается с открытой скобки, мы вызываем операторшаг (еще не реализовано), потому что оператор является следующим (+ 5 5)
Если мы получаем закрывающую скобку в качестве аргумента, мы просто отправляем ее в функцию operator, чтобы исключение было сохранено следующей функцией.
Если мы получаем пустой список со вторым параметром(остаток скобок) равным нулю, то программа синтаксически корректна, и мы просто возвращаем дерево разбора
Если значение не равно нулю, это означает, что круглые скобки не сбалансированы, если оно положительное, то открытых круглых скобок больше, а если оно отрицательное, это означает, что в выражении больше закрывающих круглых скобок.
Теперь очередь оператора
defmodule SyntaticAnalysis do
def syntatic_analysis([{:open_paren, _} | tail], parens, pt), do: operator tail, parens+1, pt
def syntatic_analysis([{:close_paren, _} | tail], parens, pt), do: operator tail, parens-1, pt
def syntatic_analysis([], 0, pt), do: pt
def syntatic_analysis([], _, _), do: raise "Open close parens not equally balanced."
def operator([{:operator, op} | tail], parens, pt), do: value(tail, parens, pt ++ [op])
def operator(_, _, _), do: raise "Operator expected."
end
Операторная функция проще предыдущей, где мы объявили всего две ветки:
Тот, который, если символ является оператором, мы вызываем значениешаг (следующая функция, которую мы собираемся объявить)
И если символ не является оператором, мы просто вызываем исключение, говорящее, что мы ожидали символ оператора.
И в завершение: шаг значения
defmodule SyntaticAnalysis do
def syntatic_analysis([{:open_paren, _} | tail], parens, pt), do: operator tail, parens+1, pt
def syntatic_analysis([{:close_paren, _} | tail], parens, pt), do: operator tail, parens-1, pt
def syntatic_analysis([], 0, pt), do: pt
def syntatic_analysis([], _, _), do: raise "Open close parens not equally balanced."
def operator([{:operator, op} | tail], parens, pt), do: value(tail, parens, pt ++ [op])
def operator(_, _, _), do: raise "Operator expected."
def value([{:number, num} | tail], parens, pt), do: value(tail, parens, pt ++ [num])
def value([{:open_paren, _} | tail], parens, pt), do: operator tail, parens+1, pt
def value([{:close_paren, _} | tail], parens, pt), do: value tail, parens-1, pt
def value([], parens, pt), do: syntatic_analysis [], parens, pt
def value(_, _, _), do: raise "Value expected."
end
Наша функция значений немного сложнее, поэтому давайте разберем ее пошагово.
Во-первых, если мы получаем токен числа, это то, что мы ожидаем, а затем мы снова вызываем шаг значение, надеясь на второе значение, окончание выражения(“ )”) или начало нового вложенного выражения (символ “(”).
Если мы получаем символ открытой скобки, мы вызываем операторstep, потому что вычисляется вложенное выражение, и увеличиваем счетчик, контролирующий баланс скобок.
Если символ является символом закрывающей скобки, мы снова вызываем value, так как это может быть конец вложенного выражения или конец программы, а баланс скобок уменьшается. в одной
Если программа представляет собой пустой список, это означает, что программа была полностью оценена, поэтому мы просто вызываем шаг syntatic_analysis для проверки конечного результата.
И наконец, если мы получаем что-то другое, мы вызываем исключение, потому что ожидалось значение.
Теперь давайте проверим окончательный результат
Бегать:
iex -S mix
Убедитесь, что вы повторили все шаги из предыдущей статьи и получили список токенов (тот, который хранится в выходной переменной).
iex(3)> program = Enum.reverse(output)
Затем нам просто нужно вызвать нашу функцию syntatic_analysis с нашим списком токенов.
iex(4)> SyntaticAnalysis.syntatic_analysis(program, 0, [])
И у нас должно получиться что-то вроде этого:
["+", "5", "5"]
И это сделано, мы удостоверились, что все символы в нашей программе следуют правильному порядку, и мы отфильтровали все необходимые и значимые символы для следующего шага (семантический анализ ).
Еще раз спасибо за ваше время, я надеюсь, что я мог изложить концепции дидактическим образом, компиляторы - нетривиальная тема, но это, безусловно, того стоит. Увидимся на следующем, пока!
