Как работать с неявным оператором 'cat' при построении синтаксического дерева для RE (используйте оценку стека) - PullRequest
Новая
       63

Как работать с неявным оператором 'cat' при построении синтаксического дерева для RE (используйте оценку стека)

0 голосов
/ 08 ноября 2018

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

Я использую различные виды узлов для представления различных типов RE. Например, SymbolExpression, CatExpression, OrExpression и StarExpression, все они являются производными от RegularExpression.

Таким образом, в стеке OPND хранится RegularExpression*. 

while(c || optr.top()):
    if(!isOp(c):
        opnd.push(c)
        c = getchar();
    else:
        switch(precede(optr.top(), c){
        case Less:
          optr.push(c)
          c = getchar();
        case Equal:
          optr.pop()
          c = getchar();
        case Greater:
          pop from opnd and optr then do operation, 
          then push the result back to opnd
        }

Но мой основной вопрос, в типичном RE, оператор cat неявный. a|bc представляет a|b.c, (a|b)*abb представляет (a|b)*.a.b.b. Итак, при встрече с не оператором, как мне сделать, чтобы определить, есть ли оператор кошка или нет? И как мне поступить с оператором cat, чтобы правильно осуществить преобразование?

Обновление

Теперь я узнал, что есть своего рода грамматика, называемая «грамматика приоритета оператора», ее оценка аналогична арифметическому выражению. Это требует, чтобы образец грамматики не мог иметь форму S -> ... AB ... (A и B не являются терминальными). Так что я думаю, что я просто не могу напрямую использовать этот метод для анализа регулярного выражения.

Обновление II

Я пытаюсь разработать грамматику LL (1) для анализа основного регулярного выражения. Вот грамматика происхождения. （\ | является escape-символом, так как | является специальным символом в шаблоне грамматики) 

E -> E \| T | T
T -> TF | F
F -> P* | P
P -> (E) | i

Чтобы удалить левую рекурсию, импортируйте новую переменную 

E -> TE'
E' -> \| TE' | ε
T -> FT'
T' -> FT' | ε
F -> P* | P   
P -> (E) | i

сейчас, для шаблона F -> P * | P ， import P '

P' -> * | ε
F -> PP'

Однако у шаблона T' -> FT' | ε есть проблема. Рассмотрим случай (a | b): 

E => TE' 
  => FT' E'
  => PT' E'
  => (E)T' E'
  => (TE')T'E'
  => (FT'E')T'E'
  => (PT'E')T'E'
  => (iT'E')T'E'
  => (iFT'E')T'E'

Здесь наш человек знает, что мы должны заменить переменную T' на T' -> ε, но программа просто вызовет T' -> FT', что неверно.

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

Ответы [ 2 ]

0 голосов
/ 12 ноября 2018

1. LL (1) грамматика

Я не вижу проблем с вашей грамматикой LL (1). Вы анализируете строку 

(a|b)

и вы дошли до этой точки: 

(a   T'E')T'E'   |b)

Символ предпросмотра - | , и у вас есть два возможных варианта: 

T' ⇒ FT'
T' ⇒ ε

FIRST (F) равно {<kbd>(</kbd>, <kbd>i</kbd>}, поэтому первая продукция явно неверна, как для человека, так и для парсера LL ( 1 ). (Парсер без предвидения не мог принять решение, но парсеры без предвкушения практически бесполезны для практического разбора.)

2. Приоритет оператора при разборе

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

Конечный автомат логически эквивалентен предварительной обработке ввода для вставки явного оператора конкатенации, где это необходимо, то есть между a и b, когда a находится в {<kbd>), <kbd>*</kbd>, <kbd>i</kbd>} и b находится в {<kbd>)</kbd>, i</kbd>}.

Вы должны принять к сведению, что ваша оригинальная грамматика на самом деле не обрабатывает регулярные выражения, если вы не дополнили ее явным & epsilon; примитив для представления пустой строки. В противном случае у вас нет возможности выразить необязательные варианты выбора, обычно представляемые в регулярных выражениях в виде неявного операнда (такого как (a|), также часто записываемого как a?). Однако конечный автомат легко способен обнаруживать неявные операнды, потому что на практике нет конфликта между неявной конкатенацией и неявным эпсилоном.

0 голосов
/ 09 ноября 2018

Я думаю, достаточно просто следить за предыдущим персонажем. Так что, если у нас есть 

(a|b)*abb
      ^--- we are here
c = a
pc = *

Мы знаем, * является унарным, поэтому «a» не может быть его операндом. Поэтому мы должны иметь конкатенацию. Аналогично на следующем шаге 

(a|b)*abb
       ^--- we are here
c = b
pc = a

a не является оператором, b не является оператором, поэтому наш скрытый оператор находится между ними. Еще один: 

(a|b)*abb
   ^--- we are here
c = b
pc = |

| - бинарный оператор, ожидающий правый операнд, поэтому мы не объединяем.

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

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

...