CFG: Почему эта грамматика неоднозначна? - PullRequest
Новая
       69

CFG: Почему эта грамматика неоднозначна?

2 голосов
/ 31 октября 2019

Грамматика выглядит следующим образом. 

S -> SS' | a | b
S' -> a | b

Как я понимаю, производные от этой грамматики будут выглядеть как SS'S'S'S'... (0 or more S'), где каждый S или S' будет генерировать a илиb.

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

1 Ответ

2 голосов
/ 31 октября 2019

Это не двусмысленно. Ваш анализ верен.

Вот механическая проверка вашей грамматики (изменена для нашего инструмента): 

S = S Sprime ;
S = a ;
S = b ;
Sprime = a ;
Sprime = b ;

Выполнение инструмента: 

C:\DMS\Domains\DMSStringGrammar\Tools\ParserGenerator>run ParserGenerator.P0B -interactive C:\
DMS GLR Parser Generator 2.4.1
Copyright (C) 1997-2018 Semantic Designs, Inc.
Opening C:\temp\Example.bnf
*** EOF seen
<<<Rule Collection Completed>>>
NTokens = 5 NRules = 5
LR(1) Parser Generator -- Find Follow and SLR Lookahead sets
Computing MemberSets for Nonterminal Tokens...

What next? ambiguities 100
Print results where (<CR> defaults to console)?
Default paper width: 80
How wide should the printout be (<CR> selects default)?
*** Search for ambiguities to depth 100

Nonterminal < Sprime > is not ambiguous
*** Search for ambiguities to depth 1; trying 2 rule pairs...
*** Search for ambiguities to depth 2; trying 2 rule pairs...
*** Search for ambiguities to depth 3; trying 2 rule pairs...
*** Search for ambiguities to depth 4; trying 2 rule pairs...
Nonterminal < S > is not ambiguous [modulo rule derivation loops]

*** 0 ambiguities found ***
*** All ambiguities in grammar detected ***

Этот инструментскорее перебор для грамматики с двумя нетерминалами. Но когда кто-то дает набор из 200 нетерминалов, это гораздо сложнее сделать вручную.

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

...