lpeg разобрать логический термин первого порядка

Question

Как видно из названия, я пытаюсь разобрать например

term(A, b, c(d, "e", 7))

в таблице Lua, как

{term, {A, b, {c, {d, "e", 7}}}}

Это грамматика, которую я построил:

local pattern = re.compile[=[
  term      <- variable / function
  argument  <- variable / lowercase /number / string
  function  <- {|lowercase {|(open argument (separator (argument / function))* close)?|}|}
  variable  <- uppercase
  lowercase <- {[a-z][A-Za-z0-9]*}
  uppercase <- {[A-Z][A-Za-z0-9]*}
  string    <- '"' {~ [^"]* ~} '"'
  number    <- {[0-9]+}
  close     <- blank ")"
  open      <- "(" blank
  separator <- blank "," blank
  blank     <- " "*
]=]

У меня следующие проблемы:

• Он не может разобрать вложенные термины. Для примера выше он возвращает только {term, {} } (пока все в порядке с term(A, b, c)).
• Чтобы удалить цитаты из строк, которые я использовал {~ ~}но из-за этого мне пришлось перенести все снимки с argument а также term в строках ниже. Есть ли способ избежать этого?
• Я хотел бы иметь ключ, связанный с каждым элементом, чтобы указать его тип, например, вместо A что-то вроде {value = "A", type = "variable"}, Я нашел способ сделать это с {:name: :} но порядок элементов в таблице теряется (потому что он не создает новую таблицу, а просто добавляет ключ, в этом случае variable="A" и порядок этих элементов не фиксирован). Как я могу пометить элементы, поддерживающие порядок?

Answer 1

В вашей грамматике у вас есть:

argument  <- variable / lowercase /number / string
function  <- {|lowercase {|(open argument (separator (argument / function))* close)?|}|}

Имейте в виду, что lpeg пытается сопоставить шаблоны / предикаты в правиле в том порядке, в котором вы их имеете. Как только он найдет совпадение, lpeg не будет рассматривать дальнейшие возможные совпадения в этом правиле грамматики, даже если позже может быть "лучшее" совпадение.

Здесь он не соответствует вызовам вложенных функций, потому что видит, что c может соответствовать

`argument  <- variable`

Так как ваш variable нетерминал указан ранее functionlpeg не учитывает последнее, и поэтому он прекращает синтаксический анализ токенов, которые идут после.

В качестве эксперимента я немного изменил вашу грамматику и добавил несколько табличных и именованных снимков для большинства интересующих вас нетерминалов.

local pattern = re.compile
[=[
  term      <- {| {:type: '' -> "term" :} term_t |}
  term_t    <- func / var
  func      <- {| {:type: '' -> "func":} {:name: func_id:} "(" arg(separator arg)* ")" |}
  func_id   <- lower / upper
  arg       <- number / string / term_t
  var       <- {| {:type: '' -> "var" :} {:name: lower / upper:} |}
  string    <- '"' {~ [^"]* ~} '"'
  lower <- {%l%w*}
  upper <- {%u%w*}
  number    <- {%d+}
  separator <- blank "," blank
  blank     <- " "*
]=]

С быстрым тестом образца:

local test = [[fun(A, b, c(d(42), "e", f, 7))]]
dump( pattern:match(test) )

Который дает следующий вывод на моей машине:

{
  {
    {
      type = "var",
      name = "A"
    },
    {
      type = "var",
      name = "b"
    },
    {
      {
        "42",
        type = "func",
        name = "d"
      },
      "e",
      {
        type = "var",
        name = "f"
      },
      "7",
      type = "func",
      name = "c"
    },
    type = "func",
    name = "fun"
  },
  type = "term"
}

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

Изменить: Вот пересмотренная грамматика, чтобы сделать анализ немного более равномерным. Я удалил term захватить, чтобы помочь удалить некоторые ненужные ветви.

local pattern2 = re.compile
[=[
  term      <- term_t
  term_t    <- func / var
  func      <- {| {:type: '' -> "func":} {:name: func_id:} "(" args? ")" |}
  func_id   <- lower / upper
  arg       <- number / string / term_t
  args      <- arg (separator args)?
  var       <- {| {:type: '' -> "var" :} {:name: lower / upper:} |}
  string    <- {| {:type: '' -> "string" :}'"' {:value: [^"]* :} '"' |}
  lower     <- {%l%w*}
  upper     <- {%u%w*}
  number    <- {| {:type: '' -> "number":} {:value: %d+:} |}
  separator <- blank "," blank
  blank     <- " "*
]=]

Что приводит к следующему:

{
  {
    type = "var",
    name = "A"
  },
  {
    type = "var",
    name = "b"
  },
  {
    {
      {
        type = "number",
        value = "42"
      },
      type = "func",
      name = "d"
    },
    {
      type = "string",
      value = "e"
    },
    {
      type = "var",
      name = "f"
    },
    {
      type = "number",
      value = "7"
    },
    type = "func",
    name = "c"
  },
  type = "func",
  name = "fun"
}

Answer 2

Извините, у меня не было опыта работы с LPeg, но обычных шаблонов Lua достаточно, чтобы легко решить вашу задачу:

local str = 'term(A, b, c(d, "e", 7))'

local function convert(expr)
    return (expr:gsub('(%w+)(%b())',
        function (name, par_expr)
            return '{'..name..', {'..convert(par_expr:sub(2, -2))..'}}'
        end
    ))
end

print(convert(str))  -- {term, {A, b, {c, {d, "e", 7}}}}

Сейчас просто load() преобразованная строка для создания таблицы.