Создание CFG, удовлетворяющего правилам

Итак, у меня есть следующая проблема: мне нужно создать контекстно-свободную однозначную грамматику, чтобы соответствовать следующим критериям.

Алфавит будет { (, a, b, ), £ }, каждая правильная строка должна включать;

  • последовательность из одного или нескольких a/b в любом порядке, они должны быть заключены в квадратные скобки ( )
  • или правильное выражение, заключенное в скобки ( и ), или их последовательность.
  • каждая правильная строка должна содержать £, и это всегда будет последний символ.

Пример правильных строк;

  • (баабб) £
  • (б)(баабб)£
  • (((аба)))£
  • ((ббаб)((б))(ба))£

Я бесчисленное количество раз пытался создать грамматику, удовлетворяющую этому требованию, и во многих случаях мне это удавалось, однако грамматика должна вести к бесконфликтной таблице разбора SR, и в каждом случае, когда я пытался, я не мог сделать ее бесконфликтной. Если у кого-нибудь есть какие-либо советы о том, как преобразовать язык, который у меня уже есть, в бесконфликтный, пожалуйста, прокомментируйте. Заранее спасибо.


language-translation grammar context-free-grammar alphabet context-free-language
person KyleB9    schedule 29.03.2021    source источник
comment
Забавно, как £ выглядит как британизированный $ или #. Разве времена кодовых страниц не прошли? (просто шутка)   -  person Maëlan    schedule 29.03.2021
comment
Вы, кажется, в основном на правильном пути с вашей последней попыткой. Но в любом случае я добавил рабочую грамматику в качестве нового ответа, который я проверил с вашими тестовыми примерами (и парой строк, которые, как я думал, следует отклонить, ab£ и ((ab)ab)£), и, похоже, это работает.   -  person rici    schedule 31.03.2021

Ответы (1)


arrow_upward
0
arrow_downward

Лучший способ решить эту проблему (и способ, с которого мне следовало бы начать) — просто воспроизвести правила как контекстно-свободную грамматику.

  1. Правильное выражение (E) — это последовательность одного или нескольких a/b (A) в любом порядке (C), заключенная в квадратные скобки ( ).

     A → a
 A → b
 C → A
 C → C A
 E → ( C )

  2. Или правильное выражение, заключенное в скобки ( ), или последовательность (S) таких

     E → ( S )
 S → S E
 S → E

  3. Каждая правильная строка должна содержать символ £, и он всегда будет последним символом.

     T → S £

Единственная часть этого, которая может нуждаться в объяснении, - это второй пункт. Обычный способ написания грамматики Дайка (то есть выражения в скобках) — с помощью правил S → ( S ) S; S → λ (где λ указывает на пустую правую часть). Но в этой задаче между скобками должно быть что-то и, видимо, есть требование, чтобы грамматика не включала λ-правила. Чтобы учесть эти требования, я разделил правило на две части: E — это одно выражение в скобках, а S — непустая последовательность.

person rici    schedule 31.03.2021
comment
Итак, используя это, я только что проверил это со следующим (a) (ab) $, но это не работает. т. е. для этого нет вывода с использованием описанной выше грамматики. Я могу добиться этого, только используя следующие правила; Стартовый символ: S S → (L)S | $ L → (L)L | (л) | Е | А Е → ЛА А → а | b, но, как я уже говорил, при использовании этой грамматики возникают конфликты SR :( - person KyleB9; 31.03.2021
comment
@ КайлБ9; возможно, я неправильно прочитал требование 2. Просто измените мое правило верхнего уровня на `T → S £` - person rici; 31.03.2021
comment
@KyleB9: я не знаю. Почему это имеет значение? - person rici; 31.03.2021