Блог

У меня есть идея для создания общей структуры синтаксического анализатора, и она работает следующим образом. В основном у вас есть грамматика, которая определяет набор правил (вложенные правила, рекурсивные правила, терминалы и т. Д.). Синтаксический анализатор рекурсивного спуска будет начинаться с основания дерева и продвигаться вниз и вниз по ветвям, а также вверх и вниз по мере прохождения дерева.

Но тогда появится второй объект определения, который кодирует иерархическую систему прослушивания событий. Он, так сказать, прослушивает переходы по правилам и выполняет код для анализа текста в этот момент анализа.

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

Пример набора правил

 math = 
  addition
  / subtraction
  / multiplication
  / division

addition =
  addition_with_parentheses
  / addition_without_parentheses

addition_with_parentheses =
  ( addition_without_parentheses )

addition_without_parentheses =
  digits   digits

digits =
  digit 

digit = 0 | 2 | 3 | 4 | 5 | ...
 

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

Пример дерева прослушивания событий

 watch math
  watch addition
    watch addition_with_parentheses
      watch digits
        watch digit
    watch addition_without_parentheses
      watch digits
        watch digit
 

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

 watch math
  watch addition
    watch addition_with_parentheses
      watch digits
        log(value)
    watch addition_without_parentheses
      watch digits
        log(value)
 

What should happen is, it should keep track of where it is in the tree of parsing in this separate object. Let’s call the even object the tracker, and the other thing the parser. The tracker should essentially listen to events from the parser in a specific context.

The parser goes something like this:

 given string
let position = 0
let start = grammar.start
check(start, string)

function check(rule, string) {
  if rule.type == 'terminal'
    rule.test(string)
  else if rule.type == 'nonterminal'
    for subrule in rule
      if check(subrule, string)
        update(position)
        continue
      else
        return false
    return true
}
 

But we augment it with the tracker thingy.

 function check(rule, string) {
  tracker.enter(rule)
  if rule.type == 'terminal'
    rule.test(string)
  else if rule.type == 'nonterminal'
    for subrule in rule
      if check(subrule, string)
        update(position)
        continue
  tracker.exit(rule)
}
 

The main part of the question is, how do you do this transitioning?

When the watch stops going any deeper, we still ned to keep track of the deepening calls. Yet only when it is back out of the hole and up to the digits level or above, we call the event handler. How do you build an algorithm for this generically? This is sort of what I have in my head so far.

 const tracker = buildTracker()

function buildTracker() {
  return {
    watchTree: {
      name: 'math',
      callback: () => console.log('x math'),
      children: [
        {
          name: 'addition',
          callback: () => console.log('x addition'),
          children: [
            {
              name: 'addition_with_parentheses',
              callback: () => console.log('x addition_with_parentheses'),
              children: [
                {
                  name: 'digits',
                  callback: () => console.log('x digits'),
                }
              ]
            },
            {
              name: 'addition_without_parentheses',
              callback: () => console.log('x addition_without_parentheses'),
              children: [
                {
                  name: 'digits',
                  callback: () => console.log('x digits'),
                }
              ]
            }
          ]
        }
      ]
    },
    stack: []
  }
}

function enter(tracker, rule) {
  if (!tracker.stack.length) {
    tracker.stack.push(tracker.watchTree)
  } else {
    const node = tracker.stack[tracker.stack.length - 1]
    const newNode = node amp;amp; node.children amp;amp; node.children.find(x => x.name === rule.name)
    if (newNode) {
      tracker.stack.push(newNode)
    } else {
      tracker.stack.push(null) // still need to keep track?
    }
  }
}

function exit(tracker, rule) {
  const node = tracker.stack.pop()
  if (node) node.callback()
}

enter(tracker, { name: 'math' })
enter(tracker, { name: 'addition' })
enter(tracker, { name: 'addition_with_parentheses' })
enter(tracker, { name: 'digits' })
enter(tracker, { name: 'digit' })
exit(tracker, { name: 'digit' })
exit(tracker, { name: 'digits' })
enter(tracker, { name: 'digits' })
enter(tracker, { name: 'digit' })
exit(tracker, { name: 'digit' })
exit(tracker, { name: 'digits' })
enter(tracker, { name: 'digits' })
enter(tracker, { name: 'digit' })
exit(tracker, { name: 'digit' })
exit(tracker, { name: 'digits' })
enter(tracker, { name: 'addition_without_parentheses' })
enter(tracker, { name: 'digits' })
enter(tracker, { name: 'digit' })
exit(tracker, { name: 'digit' })
exit(tracker, { name: 'digits' })
enter(tracker, { name: 'digits' })
enter(tracker, { name: 'digit' })
exit(tracker, { name: 'digit' })
exit(tracker, { name: 'digits' })
exit(tracker, { name: 'addition_without_parentheses' })
exit(tracker, { name: 'addition_with_parentheses' })
exit(tracker, { name: 'addition' })
exit(tracker, { name: 'math' }) 

Мы можем упростить проблему и полностью избавиться от синтаксического анализатора для целей этого вопроса. Активность анализатора может быть смоделирована путем запуска событий ввода/вывода на трекере, как показано выше.

Вопрос в том, учитывая этот поток событий, как нам обновить трекер и выполнить обратные вызовы понятным и простым способом? Я, возможно, и сделал это, но я не уверен, для меня это очень запутанно, как сделать это оптимизированным способом.