(E)BNF Как выполнить сопоставление до следующего нетерминального правила?

Question

Я пытаюсь написать грамматику для контента в формате RIS с помощью nearley

Пример файла:

TY  - JOUR
KW  - foo
KW  - bar
ER  - 

А *.ris файл всегда начинается с тега TY и заканчивается тегом ER. Между ними может быть много других тегов, напримерKW (ключевое слово).

В спецификации сказано, что один KW Оператор может занимать несколько строк.

Итак, это:

TY  - JOUR
KW  - foo
bar
baz
KW  - bat
ER  - 

Эквивалентно:

TY  - JOUR
KW  - foo bar baz
KW  - bat
ER  - 

Я изо всех сил пытаюсь придумать грамматику, которая говорила бы что-то вроде:

Ключевое слово начинается с KW с последующим - за которым следует либо:

• буквы до конца строки
• буквы до конца строки и любые другие строки до следующего ключевого слова

Что бы я ни пытался, в конечном итоге все остальные операторы "проглатываются", например, первое многострочное ключевое слово захватывает все остальное после него.

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

Answer 1

Я определенно не очень хорошо разбираюсь в грамматике (вы, наверное, догадались), но это вызвало у меня Ага- момент:

Многие люди указывали мне, что писать грамматику для Nearley сложно. Дело в том, что писать грамматики вообще очень сложно. Не помогает то, что некоторые проблемы, связанные с грамматикой, доказуемо неразрешимы.

См. https://nearley.js.org/docs/how-to-grammar-good

А также:

Использование токенизатора дает много преимуществ. Это…

• … Часто делает ваш синтаксический анализатор быстрее более чем на порядок.
• … Позволяет писать более чистые и удобные в обслуживании грамматики.
• … В некоторых случаях помогает избежать неоднозначной грамматики. [...]

См. https://nearley.js.org/docs/tokenizers.

Я знаю, что Nearley рекомендует использовать moo-lexer:

nearley поддерживает и рекомендует Moo, сверхбыстрый лексер.

См. https://nearley.js.org/docs/tokenizers.

Итак, я погуглил и нашел на YouTube этот замечательный учебник, который определенно разблокировал меня. Большое спасибо @airportyh!

Сначала я думал, что это был путь слишком сложным для моего случая использования, но оказалось, что с помощью лексера на самом деле сделал вещи возможно и проще!

---

Для простоты я предоставлю решение с усеченным файлом RIS:

sample.ris

KW  - foo
bar
baz
KW  - bat

Этот файл должен дать ['foo bar baz', 'bat'] после разбора.

Сначала давайте установим кое-что

yarn add nearley
yarn add moo

Теперь давайте определим наш лексер

lexer.js

const moo = require('moo');

const lexer =
  moo.compile
    ( { NL: {match: /[\n]/, lineBreaks: true}
      , KW: 'KW'
      , SEPARATOR: "  - "
      , CONTENT: /[a-z]+/
      }
    );

module.exports = lexer;

Мы определили четыре токена:

1. Символ новой строки NL
2. В KW ключевое слово... ключевое слово!
3. В SEPARATOR между тегом и его содержимым
4. В CONTENT тега

Теперь давайте определим нашу грамматику

grammar.ne

@{% const lexer = require('./lexer.js'); %}
@lexer lexer
@builtin "whitespace.ne"

RECORD -> _ KW:+                {% ([, keywords]) => [].concat(...keywords) %}
KW     -> %KW %SEPARATOR LINE:+ {% ([,,lines])    => lines.join(' ')        %}
LINE   -> %CONTENT __           {% ([{value}])    => value                  %}

Примечание: посмотрите, как мы можем ссылаться на токены, определенные в лексере, с помощью префикса %!

Теперь нам нужно скомпилировать нашу грамматику

Nearley поставляется с компилятором:

yarn -s nearleyc grammar.ne > grammar.js

Вы также можете определить compile сценарий в вашем package.json:

{

  ...

  "scripts": {
    "compile": "nearleyc grammar.ne > grammar.js",
  }

  ...

}

Наконец, давайте создадим парсер и воспользуемся им!

const nearley = require('nearley');
const grammar = require('./grammar.js');

module.exports =
  str => {
    const parser = new nearley.Parser(nearley.Grammar.fromCompiled(grammar));
    parser.feed(str);
    return parser.results[0];
  };

Примечание: для этого требуется скомпилированная грамматика, т.е.grammar.js

Добавим в него текст:

const parser = require('./parser.js');

parser(`
KW  - foo
bar
baz
KW  - bat
`);
//=> [ 'foo bar baz', 'bat' ]

Последний совет: вы также можете проверить свою грамматику с помощью nearley-test:

cat sample.ris | yarn -s nearley-test -- -q grammar.js