Que linguagens de computador do mundo real não podem ser descritas por gramáticas determinísticas?

7

Existem exemplos de linguagens de computador do mundo real que não são deterministas?

Por linguagens de computador eu incluo linguagens de programação, linguagens de marcação, linguagens de consulta, linguagem de modelagem, linguagens de transformação, etc.

Por não determinístico, quero dizer que eles não podem ser analisados ​​com gramáticas determinísticas.

formal-grammars programming-languages nondeterminism Máx.
fonte
Nitpick: gramáticas não analisam idiomas. Resposta: famosa, Perl não pode ser analisado em tudo .
Raphael
acho que há uma pergunta decente aqui, mas, na verdade, não existe um conceito de "gramáticas não determinísticas". como seria definido? existem autômatos não determinísticos que se correlacionam com múltiplas definições de gramáticas, etc ... também esta questão parece muito diferente para, por exemplo, RLs vs CFLs . observe que existe uma maneira de criar um DFA equivalente a partir de qualquer NFA (algoritmo padrão), portanto isso é complicado. você pode querer estudar alguma teoria CFL para tentar formular isso melhor / mais precisamente ...
vzn
Uhhh .. que provavelmente deveria ler "autômatos de empuxo não determinísticos". Mas a pergunta não tem sentido, tudo depende do tipo de análise que você espera que a análise faça. Por exemplo, reconhecer que todas as variáveis ​​são declaradas antes do uso não é livre de contexto.
reinierpost

Respostas:

4

Sim. Muitas linguagens de programação modernas possuem essa propriedade, incluindo Algol 60, C e C ++; veja abaixo para detalhes.

O Algol 60 teve o famoso problema dos outros pendentes , para alguns programas, era ambíguo como eles deveriam ser analisados ​​(que árvore de análise deveria resultar).

Muitas línguas modernas resolvem isso escolhendo uma gramática que resolve a ambiguidade de uma maneira específica. No entanto, isso requer a construção cuidadosa da gramática para eliminar a ambiguidade. Geralmente, a maneira mais natural de escrever a gramática leva a uma gramática ambígua, e você deve transformá-la para evitar a ambiguidade.

Outra abordagem é usar um analisador GLR, que pode lidar com essas gramáticas. Em seguida, você pode verificar em tempo de execução se existem vários analisadores possíveis e resolver a ambiguidade.

Outro exemplo clássico são as linguagens de programação C e C ++. A gramática de referência para C não é livre de contexto, porque quando você vê um nome, precisa saber se é o nome de um tipo ou de uma variável para saber como analisar a instrução. Por exemplo, considere a expressão

(A)*B

Se Aé uma variável, esta é a multiplicação de duas variáveis ​​e é equivalente a A*B. No entanto, se Aé o nome de um tipo, essa é uma desreferência de ponteiro e conversão de tipo (assim Bcomo um nome de variável que contém um tipo de ponteiro) e equivalente a (A) *B.

Similarmente,

A*B;

pode ser uma declaração de variável (se Aé o nome de um tipo, está declarando uma variável chamada Bcujo tipo é ponteiro para A) ou uma multiplicação (se Ae Bsão os nomes das variáveis).

Os compiladores geralmente corrigem isso incluindo código extra que "sai de cena" da linguagem das gramáticas puras e livres de contexto. Eles controlam todos os nomes de variáveis ​​e nomes de tipos no escopo e usam isso para orientar a análise em caso dessa ambiguidade. Veja o lexer hack .

Consulte também LL e LR em Contexto: Por que as ferramentas de análise são difíceis e as páginas de manual de Bison em seu analisador GLR (que inclui uma discussão de outro caso ambíguo na gramática C ++).

Por fim: acho que a pergunta tem alguma confusão sobre a diferença entre ambiguidade e não-determinismo. Autômatos e idiomas podem ser determinísticos / não determinísticos, mas não gramáticos. Gramáticas e idiomas podem ser ambíguos / inequívocos. Consulte Existem linguagens inerentemente ambíguas e deterministas sem contexto? e caracterização gramatical de linguagens determinísticas livres de contexto e Se um analisador pode analisar uma gramática não determinística, o analisador não é determinístico? . Os exemplos acima, na verdade, qualificam tanto gramáticas ambíguas quanto linguagens não determinísticas.

DW
fonte
11
este parece ser perto de uma resposta, mas a ambiguidade em línguas / lâmpadas fluorescentes compactas não é o mesmo que não determinismo ....
vzn