O que é um caso de uso no mundo real do uso de uma gramática Chomsky Tipo I (sensível ao contexto)

Ultimamente, tenho me divertido explorando o desenvolvimento de analisadores de linguagem no contexto de como eles se encaixam na Hierarquia de Chomsky.

O que é um bom exemplo do mundo real (isto é, não teórico) de uma gramática sensível ao contexto?

language-design parsing grammar Evan Plaice
fonte

A linguagem de programação conta?

Martin York

@LokiAstari Claro.

Evan Plaice

Eu acho que as linguagens de programação contam, mas não são uma boa solução, pois a complexidade da sensibilidade ao contexto é normalmente substituída por uma gramática livre de contexto com análise semântica.

31412 Frank

@Frank Acho que meu problema é que não consigo entender o que é uma linguagem sensível ao contexto sem aplicá-la a algum uso no mundo real.

Evan Plaice

Existem algumas linguagens humanas que podem não exigir analisadores de idiomas recursivamente enumeráveis e, portanto, se enquadram no conjunto de idiomas do tipo 1 (sensível ao contexto). cs.virginia.edu/~evans/cs3102/?p=138 #

Respostas:

Boa pergunta. Embora, como mencionado nos comentários, muitas linguagens de programação sejam sensíveis ao contexto, essa sensibilidade ao contexto geralmente não é resolvida na fase de análise, mas nas fases posteriores - ou seja, um superconjunto da linguagem é analisado usando uma gramática livre de contexto, e algumas dessas árvores de análise são posteriormente filtradas.

No entanto, isso não significa que essas linguagens não sejam sensíveis ao contexto , então, aqui estão alguns exemplos:

Haskell permite definir funções que são usadas como operadores e também definir a precedência e associatividade desses operadores. Em outras palavras, você não pode construir a árvore de análise correta para uma expressão de operador como:

a @@ b @@ c ## d ## e

a menos que você já tenha analisado as declarações de precedência / associatividade para @@e ##:

infixr 8 @@
infixr 6 ##

Um segundo exemplo é o Bencode , uma linguagem de dados que prefixa o conteúdo com seu comprimento:

<length>:<contents>

O problema desse formato é que é praticamente impossível analisar sem algo sensível ao contexto, porque a única maneira de descobrir os tamanhos dos "campos" é ... analisando a sequência.

Um terceiro exemplo é XML, assumindo que nomes arbitrários de tags são permitidos: os nomes de tags de abertura devem ter tags de fechamento correspondentes:

<hi>
 <bye>
 the closing tag has to match bye
 </bye>
</hi> <!-- has to match "hi" -->

fonte

Interessante. Eu sabia sobre XML. Eu suspeito que a unidade por trás da especificação XHTML 1.0 foi desviar dos intérpretes HTML do 'modo quirks' que suportam exceções sensíveis ao contexto para um XML mais limpo e livre de contexto.

Evan Plaice

@EvanPlaice Estou confuso com o seu comentário - "XML limpo" é sensível ao contexto, como mostrei no meu exemplo.

@ MattFenwick Acho que seu exemplo XML não mostra a verdadeira razão pela qual XML não é livre de contexto. O motivo é que nomes arbitrários de tags são permitidos. Se apenas um conjunto específico de tags fosse permitido, o XML seria livre de contexto.

Honza Brabec

@HonzaBrabec, você está certo - assumi implicitamente que nomes de tags arbitrários são permitidos. Eu deveria ter declarado explicitamente essa suposição. Obrigado por apontar isso!

Contanto que eu sei, gramáticas sensíveis ao contexto são usados em processamento de linguagem natural, única . Os intérpretes e compiladores das linguagens de programação não tentam analisar uma gramática livre de contexto devido à complexidade (mesmo que alguma tentativa tenha sido feita no passado).

Talvez você possa encontrar algum exemplo de uso real em uma dessas bibliotecas:

http://en.wikipedia.org/wiki/List_of_natural_language_processing_toolkits

http://opennlp.sourceforge.net/projects.html

http://nltk.org/

http://nlp.stanford.edu/nlp/javadoc/javanlp/

AlexBottoni
fonte

E o 'modo quirks' do HTML e os pré-processadores de código, eles não contam?

precisa

Gramáticas sensíveis ao contexto às vezes são usadas em descrições de semântica da linguagem de programação. Talvez o uso mais abrangente de gramáticas sensíveis ao contexto tenha sido a definição da linguagem Algol68. Ele usou uma gramática livre de contexto em dois níveis (consulte http://en.wikipedia.org/wiki/Two-level_grammar ) para descrever a sintaxe e a semântica dos programas Algol68.

Alguns de meus colegas usaram a gramática de van Wijngaarden para direcionar a implementação do Algol68 (consulte http://en.wikipedia.org/wiki/FLACC ).

BobDalgleish
fonte