Проблемы с неоднозначной грамматикой и PEG.js (примеры не найдены)

Question

Проблемы с неоднозначной грамматикой и PEG.js (примеры не найдены)

Я хочу проанализировать файл со строками следующего содержания:

simple word abbr -8. (012) word, simple phrase, one another phrase - (simply dummy text of the printing; Lorem Ipsum : "Lorem" - has been the industry's standard dummy text, ever since the 1500s!; "It is a long established!"; "Sometimes by accident, sometimes on purpose (injected humour and the like)"; "sometimes on purpose") This is the end of the line

поэтому теперь объясним части (не все пробелы описаны из-за разметки здесь):

simple word это одно или несколько слов (фраз), разделенных пробелом
abbr - является фиксированной частью строки (никогда не изменяется)
8 - необязательный номер
. - всегда включен
word, simple phrase, one another phrase - одно или несколько слов или фраз, разделенных запятой
- ( - фиксированная часть, всегда включена
simply dummy text of the printing; Lorem Ipsum : "Lorem" - has been the industry's standard dummy text, ever since the 1500s!; - (необязательно) одна или несколько фраз, разделенных ;
"It is a long established!"; "Sometimes by accident, sometimes on purpose (injected humour and the like)"; "sometimes on purpose" - (необязательно) одна или несколько фраз с кавычками "разделены по ;
) This is the end of the line - всегда включен

В худшем случае в предложении нет фраз, но это редко: должна быть фраза без кавычек (phrase1 типа) или с ними (phrase2 тип).

Таким образом, фразы являются предложениями на естественном языке (со всеми возможными пунктуацией)...

НО:

внутреннее содержание не имеет значения (т.е. мне не нужно разбирать сам естественный язык в значении НЛП)
это просто необходимо пометить его как phrase1 или же phrase2 типы:
- те, которые без и с кавычками, т. е. если фраза, которая находится между ( а также ; или же ; а также ; или же ; а также ) или даже между ( а также ) дополнен кавычками, то это phrase2 тип
- в противном случае, если фраза начинается или заканчивается без кавычек, хотя она может содержать все метки внутри фразы, это phrase1 тип

Так как писать Regex (PCRE) для такого ввода - это перебор, поэтому я обратился к подходу синтаксического анализа (EBNF или подобному). Я закончил с генератором парсера PEG.js. Я создал базовые варианты грамматики (даже не обрабатывая часть с разными фразами в предложении):

start = term _ "abbr" _ "-" .+
term = word (_? word !(_ "abbr" _ "-"))+
word = letters:letter+ {return letters.join("")}
letter = [A-Za-z]
_ "whitespace"
  = [ \t\n\r]*

или (разница только в " abbr -" а также "_ "abbr" _ "-""):

start = term " abbr -" .+
term = word (_? word !(" abbr -"))+
word = letters:letter+ {return letters.join("")}
letter = [A-Za-z]
_ "whitespace"
  = [ \t\n\r]*

Но даже эта простая грамматика не может разобрать начало строки. Ошибки:

Parse Error Expected [A-Za-z] but " " found.
Parse Error Expected "abbr" but "-" found.
и т.п.

Так что, похоже, проблема в неоднозначности: "abbr" потребляется с term как word маркер. Хотя я определил правило !(" abbr -"), который я думал, имеет значение, что следующий word токен будет использован только, если следующая подстрока не " abbr -" Добрый.

Я не нашел хороших примеров, объясняющих следующие выражения PEG.js, что представляется мне возможным решением вышеупомянутой проблемы [от: http://pegjs.majda.cz/documentation%5D:

& expression
! expression
$ expression
& { predicate }
! { predicate }

TL; DR:

связанные с PEG.js:

Есть ли примеры применения правил:
- & expression
- ! expression
- $ expression
- & { predicate }
- ! { predicate }

общий вопрос:

Каков возможный подход для обработки таких сложных строк с помощью интуитивно понятных неоднозначных грамматик? Это все еще не естественный язык, и похоже, что он имеет некоторую формальную структуру, только с несколькими дополнительными частями. Одна из идей состоит в том, чтобы разбить строки путем предварительной обработки (с помощью регулярных выражений в местах фиксированных элементов, например, "abbr -" ") Это конец строки"), а затем создать для каждой разделенной части a отдельная грамматика. Но, похоже, есть проблемы с производительностью и масштабируемостью (то есть - что, если фиксированные элементы немного изменятся - например, не будет - полукокса больше.)

Update1:

Я нашел правило, которое решает проблему с соответствием "abbr -" двусмысленность:

term = term:(word (!" abbr -" _? word))+ {return term.join("")}

но результат выглядит странно:

[
   "simple, ,word",
   " abbr -",
   [
      "8",
      ...
   ],
   ...
]

если удалить предикат: term = term:(word (!" abbr -" _? word))+:

[
   [
      "simple",
      [
         [
            undefined,
            [
               " "
            ],
            "word"
         ]
      ]
   ],
   " abbr -",
   [
      "8",
      ".",
      " ",
      "(",
      ...
   ],
   ...
]

Я ожидал что-то вроде:

[
   [
      "simple word"
   ],
   " abbr -",
   [
      "8",
      ".",
      " ",
      "(",
      ...
   ],
   ...
]

или по крайней мере:

[
   [
      "simple",
      [
         " ",
         "word"
      ]
   ],
   " abbr -",
   [
      "8",
      ".",
      " ",
      "(",
      ...
   ],
   ...
]

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

Update2:

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

start
  = (term:term1 (" abbr -" number "." _ "("number:number") "{return number}) terms:terms2 ((" - (" phrases:phrases ")" .+){return phrases}))

//start //alternative way = looks better
//  = (term:term1 " abbr -" number "." _ "("number:number") " terms:terms2 " - (" phrases:phrases ")" .+){return {term: term, number: number, phrases:phrases}}

term1
  = term1:(
    start_word:word
        (rest_words:(
          rest_word:(
            (non_abbr:!" abbr -"{return non_abbr;})
            (space:_?{return space[0];}) word){return rest_word.join("");})+{return rest_words.join("")}
        )) {return term1.join("");}


terms2
  = terms2:(start_word:word (rest_words:(!" - (" ","?" "? word)+){rest_words = rest_words.map(function(array) {
    return array.filter(function(n){return n != null;}).join("");
}); return start_word + rest_words.join("")})

phrases
//  = ((phrase_t:(phrase / '"' phrase '"') ";"?" "?){return phrase_t})+
  = (( (phrase:(phrase2 / phrase1) ";"?" "?) {return phrase;})+)

phrase2
  = (('"'pharse2:(phrase)'"'){return {phrase2: pharse2}})

phrase1
  = ((pharse1:phrase){return {phrase1: pharse1}})

phrase
  = (general_phrase:(!(';' / ')' / '";' / '")') .)+ ){return general_phrase.map(function(array){return array[1]}).join("")}

word = letters:letter+ {return letters.join("")}
letter = [A-Za-z]
number = digits:digit+{return digits.join("")}
digit = [0-9]
_ "whitespace"
  = [ \t\n\r]*

Его можно протестировать либо на сайте автора PEG.js: [ http://pegjs.majda.cz/online%5D либо на веб-IDE PEG.js: [ http://peg.arcanis.fr/%5D.

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

5

regex parsing ambiguity peg

Источник

user1309041 09 июл '14 в 17:02

1 ответ

Другие вопросы по тегам regex parsing ambiguity peg

user319698 10 июл '14 в 04:31 2014-07-10 04:31 · Answer 1 · 2014-07-10 04:31

так почему он разделен на столько уровней вложенности и даже неопределенный включен в вывод?

Если вы посмотрите документацию для PEG.js, вы увидите, что почти каждый оператор собирает результаты своих операндов в массив. undefined возвращается ! оператор.

$ оператор обходит все это вложение и просто выдает соответствующую строку, например: [a-z]+ даст массив букв, но $[a-z]+ даст строку букв.

Я думаю, что большая часть разбора здесь следует шаблону: "дай мне все, пока я не увижу эту строку". Вы должны выразить это в PEG, сначала используя ! чтобы убедиться, что вы не нажали завершающую строку, а затем просто взяли следующий символ. Например, чтобы получить все до " abbr -":

(!" abbr -" .)+

Если завершающая строка представляет собой один символ, вы можете использовать [^] как краткая форма этого, например: [^x]+ это более короткий способ сказать (!"x" .)+,

Разбирать фразы, разделенные запятой / точкой с запятой, а не фразы, заканчивающиеся запятой / точкой с запятой, немного раздражает, но кажется, что обработка их как необязательных терминаторов работает (с некоторыми trimлуг).

start = $(!" abbr -" .)+ " abbr -" $num "." [ ]? "(012)" 
  phrase_comma+ "- (" noq_phrase_semi+ q_phrase_semi+ ")"
  $.*
phrase_comma    =      p:$[^-,]+    [, ]* { return p.trim() }
noq_phrase_semi = !'"' p:$[^;]+     [; ]* { return p.trim() }
q_phrase_semi   =  '"' p:$[^"]+ '"' [; ]* { return p }
num = [0-9]+

дает

[
    "simple word",
    " abbr -",
    "8",
    ".",
    " ",
    "(012)",
    [
        "word",
        "simple phrase",
        "one another phrase"
    ],
    "- (",
    [
        "simply dummy text of the printing",
        "Lorem Ipsum : \"Lorem\" - has been the industry's standard dummy text, ever since the 1500s!"
    ],
    [
        "It is a long established!",
        "Sometimes by accident, sometimes on purpose (injected humour and the like)",
        "sometimes on purpose"
    ],
    ")",
    " This is the end of the line"
]