Простые вопросы синтаксического анализа с использованием PEG.js

Question

Я пытаюсь обернуть голову вокруг PEG, вводя простые грамматики на PEG.js площадке .

Пример 1:

• Ввод: "abcdef1234567ghijklmn8901opqrs"

• Желаемый выход: ["abcdef", "1234567", "ghijklmn", "8901", "opqrs"]

• Фактический объем производства: ["abcdef", ["1234567", ["ghijklmn", ["8901", ["opqrs", ""]]]]]

Этот пример в значительной степени работает, но можно ли заставить PEG.js не вкладывать полученный массив в миллион уровней? Я предполагаю, что хитрость заключается в том, чтобы использовать concat() вместо join() где-то, но я не могу найти место.

start
  = Text

Text
  = Numbers Text
  / Characters Text
  / EOF

Numbers
  = numbers: [0-9]+ {return numbers.join("")}

Characters
  = text: [a-z]+ {return text.join("")}

EOF
  = !.

Пример 2:

Та же проблема и код, что и в примере 1, но измените правило «Символы» на следующее, которое, как я ожидал, даст тот же результат.

Characters
  = text: (!Numbers .)+ {return text.join("")}

Результирующий вывод:

[",a,b,c,d,e,f", ["1234567", [",g,h,i,j,k,l,m,n", ["8901", [",o,p,q,r,s", ""]]]]]

Почему я получаю все эти пустые спички?

Пример 3:

Последний вопрос. Это не работает вообще. Как я могу заставить это работать? А для бонусных баллов есть какие-то указатели на эффективность? Например, следует ли мне избегать рекурсии, если это возможно?

Буду также признателен за ссылку на хороший учебник по PEG. Я прочитал (http://www.codeproject.com/KB/recipes/grammar_support_1.aspx),, но, как вы можете видеть, мне нужна дополнительная помощь ...

• Input: 'abcdefghijklmnop"qrstuvwxyz"abcdefg'
• Желаемый выход: ["abcdefghijklmnop", "qrstuvwxyz", "abcdefg"]
• Фактическая выработка: "abcdefghijklmnop\"qrstuvwxyz\"abcdefg"

start
  = Words

Words
  = Quote
  / Text
  / EOF

Quote
  = quote: ('"' .* '"') Words {return quote.join("")}

Text
  = text: (!Quote . Words) {return text.join("")}

EOF
  = !.

Answer 1

Я получил ответ в Google PEG.js, который помог мне выбрать верный путь. Я публикую ответы на все три проблемы в надежде, что они могут послужить базовым учебным пособием для других начинающих пользователей PEG, таких как я. Обратите внимание, что рекурсия не требуется.

Пример 1:

Это просто, если вы понимаете основные идиомы PEG.

start
  = Text+

Text
  = Numbers
  / Characters

Numbers
  = numbers: [0-9]+ {return numbers.join("")}

Characters
  = text: [a-z]+ {return text.join("")}

Пример 2:

Проблема здесь заключается в особом выборе дизайна в генераторе парсера PEG.js для выражений Peek (& expr и! Expr). Оба заглядывают вперед во входной поток без использования каких-либо символов, поэтому я ошибочно предположил, что они ничего не возвращали. Тем не менее, они оба возвращают пустую строку. Я надеюсь, что автор PEG.js изменит это поведение, потому что (насколько я могу судить) это просто ненужная затея, которая загрязняет выходной поток. Пожалуйста, поправьте меня, если я ошибаюсь!

В любом случае, вот обходной путь:

start
  = Text+

Text
  = Numbers
  / Words

Numbers
  = numbers: [0-9]+ {return numbers.join("")}

Words
  = text: Letter+ {return text.join("")}

Letter
  = !Numbers text: . {return text}

Пример 3:

Проблема в том, что выражение типа ('"' .* '"') никогда не может быть успешным. PEG всегда жадный, поэтому .* будет использовать остаток входного потока и никогда не увидит вторую кавычку. Вот решение (которое, между прочим, требует того же решения Peek, что и в примере 2).

start
  = Words+

Words
  = QuotedString
  / Text

QuotedString
  = '"' quote: NotQuote* '"' {return quote.join("")}

NotQuote
  = !'"' char: . {return char}

Text
  = text: NotQuote+ {return text.join("")}

Answer 2

Для текущих версий pegjs вы можете попробовать:

Пример первый

Ввод: "abcdef1234567ghijklmn8901opqrs"

Желаемый вывод: ["abcdef", "1234567", "ghijklmn", "8901", "opqrs"]

{
  /**
   * Deeply flatten an array.
   * @param  {Array} arr - array to flatten
   * @return {Array} - flattened array
   */
  const flatten = (arr) =>  Array.isArray(arr) ? arr.reduce((flat, elt) => flat.concat(Array.isArray(elt) ? flatten(elt) : elt), []) : arr
}

start = result:string {
  console.log(JSON.stringify(result))
  return result
}

string = head:chars tail:( digits chars? )* {
  return flatten([head,tail])
}

chars = [a-z]+ {
  return text()
}

digits = $[0-9]+ {
  return text()
}

Пример 2

Должно быть легко вывести из ответа выше.

Пример 3

Ввод: 'abcdefghijklmnop"qrstuvwxyz"abcdefg'

Желаемый вывод: ["abcdefghijklmnop", "qrstuvwxyz", "abcdefg"]

{
  /**
   * Deeply flatten an array.
   * @param  {Array} arr - array to flatten
   * @return {Array} - flattened array
   */
  const flatten = (arr) =>  Array.isArray(arr) ? arr.reduce((flat, elt) => flat.concat(Array.isArray(elt) ? flatten(elt) : elt), []) : arr
}

start = result:string {
  console.log(JSON.stringify(result))
  return result
}

string = head:chars tail:quote_chars* {
  return flatten([head,tail])
}

quote_chars = DQUOTE chars:chars {
  return chars
}

chars = [a-z]+ {
  return text()
}

DQUOTE = '"'

Answer 3

Пример 1

start
  = alnums

alnums
  = alnums:(alphas / numbers) {
    return alnums;
  }

alphas
  = alphas:$(alpha+)

numbers
  = numbers:$(number+)

number
  = [0-9]

alpha
  = [a-zA-Z]

Пример 2

игнорировать

Пример 3

> 'abcdefghijklmnop"qrstuvwxyz"abcdefg'.split('"')
[ 'abcdefghijklmnop',
  'qrstuvwxyz',
  'abcdefg' ]