Gramáticas ambíguas

A definição de gramáticas presta-se, com alguma facilidade, a gerar ambiguidades.

Esta característica nas linguagens humanas é por vezes procurada (onde estaria a literatura e a poesia se não fosse assim), mas geralmente é um problema.

• “Para o meu orientador, para quem nenhum agradecimento é demasiado.” “O professor falou aos alunos de engenharia” “What rimes with orange? . . . No it doesn’t!”

No caso das linguagens de programação, em que os efeitos são para ser interpretados e executados por máquinas (e não por nós), não há espaço para ambiguidades.

Assim, seja por construção da gramática, seja por regras de prioridade que lhe sejam aplicadas por omissão, as gramáticas não podem ser ambíguas.

Em ANTLR4 a definição e construção de regras define prioridades.

Analisador léxico

Se as gramáticas léxicas fossem apenas definidas por expressões regulares que competem entre si para consumir os caracteres de entrada, então elas seriam naturalmente ambíguas.

...
conditional: 'if' '(' expr ')' 'then' stat;
ID: [a-zA-Z]+;
...

Neste caso a sequência de caracteres if tanto pode dar um identificador como uma palavra reservada.

O ANTLR4 utiliza duas regras fora das expressões regulares para lidar com ambiguidade:

1. Por omissão, escolhe o token que consume o máximo número de caracteres da entrada;

2. Dá prioridade aos tokens definidos primeiro (sendo que os definidos implicitamente na gramática sintáctica têm precedência sobre todos os outros).

Analisador sintáctico

Já vimos que nas regras sintácticas também pode haver ambiguidade.

Os dois excertos seguintes exemplificam gramáticas ambíguas:

stat: ID '=' expr
    | ID '=' expr
    ;
expr: NUM
    ;

stat: expr ';'
    | ID '(' ')' ';'
    ;
expr: ID '(' ')'
    | NUM
    ;

Em ambos os casos a ambiguidade resulta de ser ter uma sub-regra repetida, directamente, no primeiro caso, e indirectamente, no segundo caso.

A gramática diz-se ambígua porque, para a mesma entrada, poderíamos ter duas árvores sintácticas diferentes.

O ANTLR4 tem regras adicionais para eliminar ambiguidades sintácticas.

Tal como no analisador léxico, regras Ad hoc fora da notação das gramática independentes de contexto, garantem a não ambiguidade.

Essas regras são as seguintes:

1. As alternativas, directa ou indirectamente, definidas primeiro têm precedência sobre as restantes.

2. Por omissão, a associatividade de operadores é à esquerda.

Das duas árvores sintácticas apresentadas no exemplo anterior, a gramática definida impõe a primeira alternativa.