Грамматика неоднозначна или не слишком неоднозначна?

Question

Я новичок в BNF, у меня есть вопрос, который нужно решить. Ниже приводится вопрос.

«Для каждого из следующих грамматик укажите, являются ли они двусмысленными или однозначными».

Grammar1:

<T> ::= <T> <Q> 0 | 22 
<Q> ::= 2|3 

Grammar2:

<first>::=<first><first><second> 
<second>::=<third><second> 
<third>::=a|b|c 

Grammar3:

<A>::=<B><A><A> 
<B>::=1|2|3|4 

может кто-то пожалуйста, помогите мне найти ответы и описать таким образом, легко понять, что это большая помощь. так пожалуйста.

Answer 1

Чтобы обнаружить двусмысленность в грамматике, вам необходимо выставить строку, которая может быть проанализирована двумя способами.

Поиск такой струны может быть трудным с большой грамматикой; на самом деле это невозможно.

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

Что вы действительно хотите сделать, это создать инструмент, который перечисляет возможные строки символов и пытается их увидеть, есть ли двусмысленность.

Вы можете сделать эту грубую силу, просто генерируя все строки, но это быстро создает много строк, которые просто не поддаются анализу, и это не помогает.

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

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

1. Pick a pair of rules with the same LHS. 
2. Instantiate S1 with the RHS of the first rule, S2 with the RHS of the second. 
3. Repeat until you are tired (hit some search depth): 
    a. if s1 == s2, you've found an ambiguity. 
    b. if s1 derives a terminal that s2 does not derive, 
     then s1 and s2 cannot be ambiguous. 
    c. Pick a nonterminal in s1 or s2. 
     If there is none, then if s1 <> s2, this path doesn't lead to an ambiguity: backtrack. 
    d. Replace the nonterminal with a valid RHS for that nonterminal. 
    e. Recurse to a. 
4. If all branches of the search lead to non-ambiguous strings, 
    then this rule isn't ambiguous. 

СМТН Software Реинжиниринг Инструментарий имеет парсер генератор с такой возможностью, построенной в; мы можем просто попробовать грамматики. Я должен был немного переформулировать грамматик, чтобы сделать их совместимыми с DMS, поэтому я показываю новую версию здесь:

Grammar1:

<T> ::= <T><Q> '0' ; 
<T> ::= '2' '2' ; 
<Q> ::= '2' ; 
<Q> ::= '3' ; 

DMS работать на Grammar1:

C:\DMS\Domains\DMSStringGrammar\Tools\ParserGenerator\Source>run ..\ParserGenerator.P0B -interactive \temp\Grammar1.bnf 
DMS GLR Parser Generator 2.3.5 
Copyright (C) 1997-2017 Semantic Designs, Inc. 
<<<Rule Collection Completed>>> 
NTokens = 6 NRules = 4 
*** LR(0) State Machine construction complete *** 
States: 8 
What next? ambiguities 10 
Nonterminal <Q> is not ambiguous 
*** Search for ambiguities to depth 1... 
*** Search for ambiguities to depth 2... 
*** Search for ambiguities to depth 3... 
*** Search for ambiguities to depth 4... 
Nonterminal <T> is not ambiguous 
*** All ambiguities in grammar detected *** 

инструмент сообщает, что все нетерминалы не являются двусмысленными. Итак, Grammar1 не является двусмысленным.

Grammar2:

<first> = <first><first><second> ; 
<second> = <third><second> ; 
<third> = 'a' ; 
<third> = 'b' ; 
<third> = 'c' ; 

DMS работает на Grammar2:

C:\DMS\Domains\DMSStringGrammar\Tools\ParserGenerator\Source>run ..\ParserGenerator.P0B -interactive \temp\Grammar2.bnf 
DMS GLR Parser Generator 2.3.5 
Copyright (C) 1997-2017 Semantic Designs, Inc. 
<<<Rule Collection Completed>>> 
NTokens = 7 NRules = 5 
*** LR(0) State Machine construction complete *** 
Determining if machine is SLR(0), SLR(1) or LALR(1)... 
States: 9 
Detecting possible cycles... 

*** Circular definition: 
Rule 1: <first> = <first> <first> <second> ; 

*** Circular definition: 
Rule 2: <second> = <third> <second> ; 

What next? ambiguities 10 
Nonterminal <first> is circularly defined 
Nonterminal <second> is circularly defined 
Nonterminal <third> is not ambiguous 
*** Search for ambiguities to depth 1... 
*** All ambiguities in grammar detected *** 

Эта грамматика проблема OP не спрашивал о: маркеры <first> и <second> плохо определены («круговое определение» в соответствии с этим инструментом). Должно быть ясно, что <first> разворачивает начало с <first>, но ничего не дает сообщить нам, что <first> может быть расшифрован как конкретный литерал. Итак, грамматика не двусмысленная ... она просто прямая сломанной.

Grammar3:

<A> = <B><A><A> ; 
<B> = '1' ; 
<B> = '2' ; 
<B> = '3' ; 
<B> = '4' ; 

DMS работает на Grammar3:

C:\DMS\Domains\DMSStringGrammar\Tools\ParserGenerator\Source>run ..\ParserGenerator.P0B -interactive \temp\Grammar3.bnf 
DMS GLR Parser Generator 2.3.5 
Copyright (C) 1997-2017 Semantic Designs, Inc. 
<<<Rule Collection Completed>>> 
NTokens = 7 NRules = 5 
LR(0) State Machine Generation Phase. 
*** LR(0) State Machine construction complete *** 

States: 8 

Detecting possible cycles... 

*** Circular definition: 
Rule 1: <A> = <B> <A> <A> ; 

What next? ambiguities 10 
Nonterminal <A> is circularly defined 
Nonterminal <B> is not ambiguous 
*** Search for ambiguities to depth 1... 
*** All ambiguities in grammar detected *** 

Эта грамматика также нарушена в пути ОП не обсуждали. Здесь проблема в том, что мы можем найти замену для <A>, но это приводит к бесконечному расширению. Грамматика не является двусмысленной, но она только принимает бесконечно длинные строки, которые на практике не полезны.

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

Grammar4:

G = S ; 
S = 'if' E 'then' S ; 
S = 'if' E 'then' S 'else' S ; 
S = V '=' E ; 

ТСС Запуск на Grammar4:

C:\DMS\Domains\DMSStringGrammar\Tools\ParserGenerator\Source>run ..\ParserGenerator.P0B -interactive ..\Tests\ifthenelse_ambiguous.bnf 
DMS GLR Parser Generator 2.3.5 
Copyright (C) 1997-2017 Semantic Designs, Inc. 
Opening ..\Tests\ifthenelse_ambiguous.bnf 
<<<Rule Collection Completed>>> 
NTokens = 9 NRules = 4 
*** LR(0) State Machine construction complete *** 

What next? ambiguities 10 

Nonterminal G is not ambiguous 
*** Search for ambiguities to depth 1... 
*** Search for ambiguities to depth 2... 

Ambiguous Rules: 
S = 'if' E 'then' S 'else' S ; SemanticCopy2 
S = 'if' E 'then' S ; SemanticCopy2 
Instance: < 'if' E 'then' 'if' E 'then' S 'else' S > 
Derivation: 
1: < S 'else' S > 
    <S> 
2: < 'if' E 'then' S 'else' S > 
    < 'if' E 'then' S 'else' S > 
*** All ambiguities in grammar detected *** 

поиск находит неоднозначную фразу выражения для утверждения. Если вы смотрите на фразу примера, вы должны увидеть, что есть одно предложение else ... и грамматика позволяет привязать себя к инструкции if-then.

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

Рассмотрим бег на грамматику Java версии 8, с более чем 400 правил:

C:\DMS\Domains\DMSStringGrammar\Tools\ParserGenerator\Source>run ..\ParserGenerator.P0B -interactive "C:\DMS\Domains\Java\v8\tools\Parser\Source\Syntax\%Java~v8.bnf" 
DMS GLR Parser Generator 2.3.5 
Copyright (C) 1997-2017 Semantic Designs, Inc. 
Opening C:\DMS\Domains\Java\v8\tools\Parser\Source\Syntax\%Java~v8.bnf 
<<<Rule Collection Completed>>> 
NTokens = 243 NRules = 410 
*** LR(0) State Machine construction complete *** 
States: 774 

What next? ambiguities 15 

Nonterminal optional_CONTROL_Z is not ambiguous 
Nonterminal package_name_declaration is not ambiguous 
Nonterminal anonymous_class_creation is not ambiguous 
Nonterminal annotation_type_declaration is not ambiguous 
Nonterminal annotation_interface_header is not ambiguous 
Nonterminal default_value is not ambiguous 
Nonterminal field_declaration is not ambiguous 
Nonterminal member_value is not ambiguous 
Nonterminal marker_annotation is not ambiguous 
Nonterminal single_member_annotation is not ambiguous 
Nonterminal enum_body is not ambiguous 
Nonterminal type_parameters is not ambiguous 
Nonterminal modifier is not ambiguous 
Nonterminal local_variable_declaration is not ambiguous 
Nonterminal vararg_parameter is not ambiguous 
Nonterminal variable_declarator_id is not ambiguous 
Nonterminal variable_initializer is not ambiguous 
Nonterminal primitive_type is not ambiguous 
Nonterminal try_resource_list_opt is not ambiguous 
Nonterminal catch_statements_opt is not ambiguous 
Nonterminal finally_statement_opt is not ambiguous 
Nonterminal finally_statement is not ambiguous 
Nonterminal switch_group is not ambiguous 
Nonterminal switch_label is not ambiguous 
Nonterminal catch_statement is not ambiguous 
Nonterminal catch_parameter is not ambiguous 
Nonterminal literal is not ambiguous 
Nonterminal array_dims is not ambiguous 
Nonterminal array_creation_with_initialization is not ambiguous 
Nonterminal dim_spec is not ambiguous 
Nonterminal superpath is not ambiguous 
Nonterminal thispath is not ambiguous 
Nonterminal target is not ambiguous 
Nonterminal unary_expression is not ambiguous 
Nonterminal lambda_body is not ambiguous 
Nonterminal right_angle is not ambiguous 
*** Search for ambiguities to depth 1... 
Nonterminal type_declarations is not ambiguous 
Nonterminal annotations_opt is not ambiguous 
Nonterminal modifiers is not ambiguous 
Nonterminal brackets is not ambiguous 
Nonterminal switch_groups is not ambiguous 
Nonterminal bounds_list is not ambiguous 
*** Search for ambiguities to depth 2... 
Nonterminal class_body is not ambiguous 
Nonterminal arguments is not ambiguous 
Nonterminal annotation_type_body is not ambiguous 
Nonterminal qualified_name is not ambiguous 
Nonterminal interface_body is not ambiguous 
Nonterminal enum_class_header is not ambiguous 
Nonterminal enum_class_body_opt is not ambiguous 
Nonterminal block is not ambiguous 

Ambiguous Rules: 
executable_statement = 'if' '(' expression ')' executable_statement 'else' executable_statement ; SemanticCopy2 
executable_statement = 'if' '(' expression ')' executable_statement ; SemanticCopy2 
Instance: < 'if' '(' expression ')' 'if' '(' expression ')' executable_statement 'else' executable_statement > 
Derivation: 
1: < executable_statement 'else' executable_statement > 
<executable_statement> 
2: < 'if' '(' expression ')' executable_statement 'else' executable_statement > 
< 'if' '(' expression ')' executable_statement 'else' executable_statement > 
Nonterminal variable_declarator is not ambiguous 
Nonterminal try_resource_list is not ambiguous 
*** Search for ambiguities to depth 3... 
Nonterminal type_arguments is not ambiguous 
Nonterminal member_value_pair is not ambiguous 
*** Search for ambiguities to depth 4... 
Nonterminal array_creation_no_initialization is not ambiguous 
Nonterminal array_creation_with_initialization_header is not ambiguous 
*** Search for ambiguities to depth 5... 
Nonterminal compilation_unit is not ambiguous 
Nonterminal nested_class_declaration is not ambiguous 
Nonterminal interface_header is not ambiguous 
*** Search for ambiguities to depth 6... 
Nonterminal name is not ambiguous 
Nonterminal normal_annotation is not ambiguous 
Nonterminal type_parameter is not ambiguous 
*** Search for ambiguities to depth 7... 
Nonterminal enum_constant is not ambiguous 
Nonterminal bound is not ambiguous 
*** Search for ambiguities to depth 8... 
Nonterminal annotation is not ambiguous 
Nonterminal type is not ambiguous 
Nonterminal catch_statements is not ambiguous 
Nonterminal value_suffix is not ambiguous 

Ambiguous Rules: 
method_reference = type '::' type_arguments IDENTIFIER ; SemanticCopy2 
method_reference = primary '::' type_arguments IDENTIFIER ; SemanticCopy2 
Instance: < IDENTIFIER '::' type_arguments IDENTIFIER > 
Derivation: 
1: < type '::' type_arguments IDENTIFIER > 
< primary '::' type_arguments IDENTIFIER > 
2: <type> 
<primary> 
3: < name brackets > 
<primary> 
4: < annotations_opt IDENTIFIER type_arguments brackets > 
<primary> 
5: < IDENTIFIER type_arguments brackets > 
<primary> 
6: < IDENTIFIER type_arguments brackets > 
<primary_not_new_array> 
7: < IDENTIFIER type_arguments brackets > 
<IDENTIFIER> 
8: < type_arguments brackets > 
< > 
*** Search for ambiguities to depth 9... 
Nonterminal enum_constants is not ambiguous 
Nonterminal type_argument is not ambiguous 
*** Search for ambiguities to depth 10... 
Nonterminal parameter is not ambiguous 
*** Search for ambiguities to depth 11... 
Nonterminal class_header is not ambiguous 
Nonterminal nested_interface_declaration is not ambiguous 
*** Search for ambiguities to depth 12... 
Nonterminal import_statement is not ambiguous 
Nonterminal type_declaration is not ambiguous 
Nonterminal name_list is not ambiguous 
Nonterminal variable_declarator_list is not ambiguous 
Nonterminal formal_name_list is not ambiguous 
*** Search for ambiguities to depth 13... 
*** Search for ambiguities to depth 14... 
Nonterminal method_declaration is not ambiguous 

Это занимает около 5 минут, чтобы работать, потому что это вычисление экспоненциально растет множество экземпляров строк. Но мы узнаем:

1) У Java тоже есть проблема с болтанием! (В наших синтаксических анализах мы обрабатываем этим правилом «предпочитаем смену« еще », который этот детектор неопределенности не знает.

2) Правило грамматики для method_reference неоднозначно. Я думаю, так и в самом Java-стандарте. На самом деле это , обработанный в наших синтаксических анализаторах в названии resolver, глядя на тип IDENTIFIER.

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