Сдвиг / уменьшение конфликта с неоднозначной грамматикой

Question

Сдвиг / уменьшение конфликта с неоднозначной грамматикой

Я застрял с некоторой неоднозначной грамматикой на некоторое время, поскольку yacc сообщает о 6 конфликтах сдвига / уменьшения. Я посмотрел в файле y.output и попытался понять, как смотреть на состояния и выяснить, что делать, чтобы исправить неоднозначную грамматику, но безрезультатно. Я законно застрял в том, как я должен решить проблемы. Я посмотрел на множество вопросов о переполнении стека, чтобы понять, помогут ли объяснения других людей мне с моей проблемой, но это также не сильно помогло мне. Для записи, я не могу использовать какие-либо директивы, определяющие приоритет, такие как %left разрешить разбор конфликтов.

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

В любом случае, вот моя грамматика под вопросом (это небольшое расширение грамматики MiniJava):

Grammar
0 $accept: program $end

1 program: main_class class_decl_list

2 main_class: CLASS ID '{' PUBLIC STATIC VOID MAIN '(' STRING '[' ']' ID ')' '{' statement '}' '}'

3 class_decl_list: class_decl_list class_decl
4                | %empty

5 class_decl: CLASS ID '{' var_decl_list method_decl_list '}'
6           | CLASS ID EXTENDS ID '{' var_decl_list method_decl_list '}'

7 var_decl_list: var_decl_list var_decl
8              | %empty

9 method_decl_list: method_decl_list method_decl
10                 | %empty

11 var_decl: type ID ';'

12 method_decl: PUBLIC type ID '(' formal_list ')' '{' var_decl_list statement_list RETURN exp ';' '}'

13 formal_list: type ID formal_rest_list
14            | %empty

15 formal_rest_list: formal_rest_list formal_rest
16                 | %empty

17 formal_rest: ',' type ID

18 type: INT
19     | BOOLEAN
20     | ID
21     | type '[' ']'

22 statement: '{' statement_list '}'
23          | IF '(' exp ')' statement ELSE statement
24          | WHILE '(' exp ')' statement
25          | SOUT '(' exp ')' ';'
26          | SOUT '(' STRING_LITERAL ')' ';'
27          | ID '=' exp ';'
28          | ID index '=' exp ';'
29 statement_list: statement_list statement
30               | %empty

31 index: '[' exp ']'
32      | index '[' exp ']'

33 exp: exp OP exp
34    | '!' exp
35    | '+' exp
36    | '-' exp
37    | '(' exp ')'
38    | ID index
39    | ID '.' LENGTH
40    | ID index '.' LENGTH
41    | INTEGER_LITERAL
42    | TRUE
43    | FALSE
44    | object
45    | object '.' ID '(' exp_list ')'

46 object: ID
47       | THIS
48       | NEW ID '(' ')'
49       | NEW type index

50 exp_list: exp exp_rest_list
51         | %empty

52 exp_rest_list: exp_rest_list exp_rest
53              | %empty
54 exp_rest: ',' exp

И вот соответствующие состояния из y.output, которые имеют конфликты сдвига / уменьшения.

State 58
7 var_decl_list: var_decl_list . var_decl
12 method_decl: PUBLIC type ID '(' formal_list ')' '{' var_decl_list . statement_list RETURN exp ';' '}'

INT      shift, and go to state 20
BOOLEAN  shift, and go to state 21
ID       shift, and go to state 22

ID        [reduce using rule 30 (statement_list)]
$default  reduce using rule 30 (statement_list)

var_decl        go to state 24
type            go to state 25
statement_list  go to state 69


State 76
38 exp: ID . index
39    | ID . '.' LENGTH
40    | ID . index '.' LENGTH
46 object: ID .

'['  shift, and go to state 64
'.'  shift, and go to state 97

'.'       [reduce using rule 46 (object)]
$default  reduce using rule 46 (object)

index  go to state 98


State 100
33 exp: exp . OP exp
34    | '!' exp .

OP  shift, and go to state 103

OP        [reduce using rule 34 (exp)]
$default  reduce using rule 34 (exp)


State 101
33 exp: exp . OP exp
35    | '+' exp .

OP  shift, and go to state 103

OP        [reduce using rule 35 (exp)]
$default  reduce using rule 35 (exp)


State 102
33 exp: exp . OP exp
36    | '-' exp .

OP  shift, and go to state 103

OP        [reduce using rule 36 (exp)]
$default  reduce using rule 36 (exp)


State 120
33 exp: exp . OP exp
33    | exp OP exp .

OP  shift, and go to state 103

OP        [reduce using rule 33 (exp)]
$default  reduce using rule 33 (exp)

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

0

parsing yacc shift-reduce-conflict

Источник

user8638531 18 фев '19 в 21:16

1 ответ

Решение

Другие вопросы по тегам parsing yacc shift-reduce-conflict

user16406 18 фев '19 в 22:20 2019-02-18 22:20 · Accepted Answer · 2019-02-18 22:20

Основная проблема заключается в том, что при разборе method_decl тело, это не может сказать, где var_decl_list заканчивается и statement_list начинается. Это потому, что когда ID, он не знает, является ли это началом другого var_decl или начало первого statementи ему нужно уменьшить пустой оператор, прежде чем он сможет начать работать над statement_list,

Есть несколько способов справиться с этим:

пусть лексер вернет разные токены для идентификаторов типов и других идентификаторов - таким образом, различие сообщит парсеру, который следующий.
не требует пустого оператора в начале списка операторов. Измените грамматику на:
```
statement_list: statement | statement_list statement ;
opt_statement_list: statement_list | %empty ;
```
и использовать opt_statement_list в method_decl править. Это обходит проблему необходимости уменьшить пустой statement_list прежде чем начать разбор заявлений. Это процесс, известный как "unfactoring" грамматика, поскольку вы заменяете правила несколькими вариантами. Это делает грамматику более сложной, и в этом случае не решает проблему, она просто перемещает ее; тогда вы увидите сдвиг / уменьшение конфликтов между statement: ID . index а также type: ID на [ смотреть вперед. Эта проблема также может быть решена с помощью unfactoring, но сложнее.

Таким образом, это приводит к общей идее разрешения конфликтов между сдвигами и сокращениями путем несанкционированного использования. Основная идея состоит в том, чтобы избавиться от правила, вызывающего уменьшение половины сдвига, уменьшить конфликт, заменив его правилами, которые более ограничены в контексте, поэтому не инициируйте конфликт. Приведенный выше пример легко решается с помощью "заменить рекурсивный повтор 0 или более рекурсивным повтором 1 или более и необязательным правилом". Это хорошо работает для конфликтов сдвига-уменьшения в правиле epsilon повтора, если следующий контекст означает, что вы можете легко разрешить, когда 0-регистр должен быть допустимым (только когда следующий токен } в этом случае.)

Второй конфликт сложнее. Здесь конфликт заключается в сокращении type: ID когда предвкушение [, Поэтому нам нужно дублировать правила типов, пока в этом нет необходимости. Что-то вроде:

type: simpleType | arrayType ;
simpleType: INT | BOOLEAN | ID ;
arrayType: INT '[' ']' | BOOLEAN '[' ']' | ID '[' ']'
         | arrayType '[' ']' ;

заменяет "0 или более повторений '[' ']' суффикс "с" 1 или более "и работает по аналогичным причинам (откладывает сокращение до тех пор, пока '[' ']' вместо того, чтобы требовать это раньше.) Ключ в том, что simpleType: ID Правило никогда не должно быть уменьшено, когда '[' поскольку это действительно только в других контекстах.