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

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)

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

Answer 1

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

---

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

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

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

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