Упрощение грамматики без контекста (красивее)

Question

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

S->tooooooo much stuff

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

т.е. lang:

a^n b^m, where n >= m

Мой CFG (брутто):

S -> Sa|Sab|Sba|aS|aSb|abS|bSa|baS|ε

Может ли кто-нибудь помочь мне с моими вредными привычками?

Answer 1

Вам действительно нужно использовать CFG для описания этого простого языка? Было бы намного проще просто сосчитать a и b.

Но при условии, что это всего лишь пример ...

CFG в реальных синтаксических анализаторах обычно разбивают его до одного производства на строку и группируют их некоторым разумным способом.

S -> a b S
   | b a S
   | a S
   | a S b
   | b S a
   | ε