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

Question

Я пытаюсь построить синтаксическое дерево для регулярного выражения. Я использую стратегию, аналогичную оценке арифметических выражений (я знаю, что существуют способы, подобные рекурсивному спуску), то есть использую два стека, стек 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， импорт 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', что не так.

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

Answer 1

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

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

(a|b)

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

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

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

T' ⇒ FT'
T' ⇒ ε

ПЕРВЫЙ (F) {(, i}Таким образом, первая продукция явно неверна, как для человека, так и для парсера LL (1). (Парсер без предвкушения не может принять решение, но парсеры без предвкушения практически бесполезны для практического разбора.)

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

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

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

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

Answer 2

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

(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, что звучит больно, но это должно дать вам достаточно контекста, чтобы пройти.

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