Gramática não contextual

Na ciência da computação linguística e teórica , uma gramática livre de contexto , ou gramática livre de contexto , também chamada de gramática livre de contexto ou gramática "livre de contexto" é uma gramática formal em que cada regra de produção tem a forma

X→α{\ displaystyle X \ to \ alpha}

onde é um símbolo não terminal e é uma string que consiste em terminais e / ou não terminais. O termo “não contextual” vem do fato de que um não terminal pode ser substituído por , independentemente do contexto em que aparece. Uma linguagem formal é não contextual (ou fora de contexto, ou mesmo algébrica) se houver uma gramática não contextual que a gera. X{\ displaystyle X}α{\ displaystyle \ alpha}X{\ displaystyle X}α{\ displaystyle \ alpha}

Em contraste, uma regra do formulário é contextual

vs +X→vs+α{\ displaystyle c ~ + X \ a c + \ alpha}

devido à parte esquerda da regra que indica um contexto para X. Tal regra significa que X, no caso (contexto) em que é precedido pelo símbolo do terminal e pelo literal , pode ser substituído por . vs{\ displaystyle c}+{\ displaystyle +}α{\ displaystyle \ alpha}

Assim, em uma gramática não contextual , um símbolo não terminal está sempre sozinho na parte esquerda de qualquer regra, o que significa que seu ambiente sintático (ou contexto) não é considerado.

Gramáticas algébricas são poderosas o suficiente para descrever a parte principal da sintaxe da maioria das linguagens de programação , com algumas extensões conforme necessário. A forma Backus-Naur é a notação mais comum usada para descrever uma gramática não contextual que descreve uma linguagem de programação. Na hierarquia de Chomsky , essas gramáticas são do tipo 2.

Se encontrarmos vários termos para nomear uma gramática algébrica, é porque o termo em inglês “  livre de contexto  ” é difícil de traduzir. Todos os termos fornecidos acima são usados ​​e equivalentes.

Definições formais

Uma gramática algébrica é composta: G{\ displaystyle G}

• um alfabeto finito de símbolos não terminais ou variáveis  ;V{\ displaystyle V}
• de um alfabeto finito , separado de , de símbolos terminais ou letras terminais  ;NO{\ displaystyle A}V{\ displaystyle V}
• de um elemento de chamado de axioma  ;S{\ displaystyle S}V{\ displaystyle V}
• de um conjunto finito de regras de derivações ou produções .P⊂V×(V∪NO)∗{\ displaystyle {\ mathcal {P}} \ subset V \ times (V \ cup A) ^ {*}}

Uma regra geralmente é escrita no formulário . A variável e a palavra são chamadas de membro esquerdo e direito da regra, respectivamente. Estendemos essa notação e escrevemos quando resulta da substituição, em , de um membro esquerdo da regra (que é, portanto, uma variável) por seu membro direito, portanto, se houver palavras e uma regra como e . Notamos o fechamento reflexivo e transitivo dessa relação. Quando (X,α){\ displaystyle (X, \ alpha) \,}X→α{\ displaystyle X \ to \ alpha}X{\ displaystyle X}α{\ displaystyle \ alpha}você→v{\ displaystyle u \ to v}v{\ displaystyle v}você{\ displaystyle u}você{\ displaystyle u}x,y{\ displaystyle x, y}X→α{\ displaystyle X \ to \ alpha}você=xXy{\ displaystyle u = xXy}v=xαy{\ displaystyle v = x \ alpha y}→∗{\ displaystyle {\ stackrel {*} {\ to}}}

você→∗v{\ displaystyle u {\ stackrel {*} {\ to}} v},

dizemos que deriva no . você{\ displaystyle u} v{\ displaystyle v}

A linguagem gerada pela gramática , notada , é o conjunto de palavras terminais (não mais contendo variáveis) que derivam do axioma , ou seja, G{\ displaystyle G}eu(G){\ displaystyle L (G)}S{\ displaystyle S}

eu(G)={C∈NO∗∣S→∗C}{\ displaystyle L (G) = \ {w \ in A ^ {*} \ mid S {\ stackrel {*} {\ to}} w \}}.

Chamamos de linguagem algébrica ou linguagem não contextual uma linguagem que pode ser gerada por uma gramática algébrica. A "  linguagem expandida  " gerado pela gramática consiste em todas as palavras de que derivam do axioma , mesmo contendo variáveis. C{\ displaystyle w}NO∪V{\ displaystyle A \ cup V}S{\ displaystyle S}

Exemplos

Exemplo 1

Considere a seguinte gramática algébrica:

S→noSbS→ε{\ displaystyle {\ begin {array} {l} S \ to aSb \\ S \ to \ varepsilon \ end {array}}}

onde denota a palavra vazia. Essa gramática gera uma linguagem que não é uma linguagem racional . ε{\ displaystyle \ varepsilon}{nonãobnão∣não≥0}{\ displaystyle \ {a ^ {n} b ^ {n} \ mid n \ geq 0 \}}

Também podemos usar uma barra vertical para agrupar as regras com o mesmo símbolo não terminal do membro esquerdo e escrever a gramática na seguinte forma condensada:

S→noSb∣ε{\ displaystyle S \ a aSb \ mid \ varepsilon}.

Exemplo 2

Aqui é uma gramática algébrica que gera as expressões aritméticas em três variáveis , e , corretamente entre parênteses: x{\ displaystyle x}y{\ displaystyle y}z{\ displaystyle z}

S→x∣y∣z∣S+S∣S-S∣S∗S∣S/S∣(S){\ displaystyle S \ a x \ mid y \ mid z \ mid S + S \ mid SS \ mid S * S \ mid S / S \ mid (S)}

Esta gramática gera, por exemplo . (x+y)∗x-z∗y/(x+x){\ displaystyle (x + y) * xz * y / (x + x)}

Exemplo 3

A gramática a seguir gera o idioma composto pelas palavras en e en , e cujo número de é diferente do número de  : no{\ displaystyle a}b{\ displaystyle b}no{\ displaystyle a}b{\ displaystyle b}

S→você∣V{\ displaystyle S \ a U \ mid V} você→Tnovocê∣TnoT{\ displaystyle U \ to TaU \ mid TaT} V→TbV∣TbT{\ displaystyle V \ to TbV \ mid TbT} T→noTbT∣bTnoT∣ε{\ displaystyle T \ a aTbT \ mid bTaT \ mid \ varepsilon}

T{\ displaystyle T}produz palavras com o mesmo número de e's , produz palavras com mais que e produz palavras com menos que . no{\ displaystyle a}b{\ displaystyle b}você{\ displaystyle U}no{\ displaystyle a}b{\ displaystyle b}V{\ displaystyle V}no{\ displaystyle a}b{\ displaystyle b}

Exemplo 4

As línguas de Dyck ou as línguas de palavras bem colocadas entre parênteses são línguas algébricas.

Outro exemplo

Gramáticas não contextuais não se limitam a linguagens formais em matemática. Eles também são usados ​​em linguística, embora as gramáticas contextuais sejam frequentemente mais adequadas. Um exemplo notável é o trabalho do linguista indiana Panini , asset IV ª  século  aC. AD Ele descreveu a gramática do Sânscrito em um sistema altamente formalizado, com quase 4000 regras. Essas regras são apresentadas em uma notação próxima à forma de Backus-Naur .

Filiais e galhos de árvores

Existem duas maneiras de descrever como uma palavra foi gerada a partir de uma dada gramática, a primeira consiste em listar a sequência de mapeamentos das regras, a segunda sintetiza essa lista em uma árvore, chamada de árvore de derivação.

O primeiro método lista a sequência de palavras (começando com o símbolo inicial, o axioma, e terminando com a palavra pesquisada). Palavras intermediárias, contendo variáveis, às vezes são chamadas de proto-sentenças ( formas sentenciais em inglês) ou palavra de linguagem estendida . Além dessas palavras, listamos as regras aplicadas para passar de uma palavra para a próxima. Se, além disso, usarmos a estratégia que consiste em "substituir sempre o não terminal mais à esquerda", então é suficiente fornecer a lista das regras aplicadas. A derivação obtida é chamada de derivação esquerda da palavra. Por exemplo, para a seguinte gramática:

(1)S→S+S{\ displaystyle (1) \ quad S \ a S + S} (2)S→no{\ displaystyle (2) \ quad S \ a a} (3)S→1{\ displaystyle (3) \ quad S \ a 1}

a string "   ", portanto, admite várias derivações. A derivação representada pela lista [(1), (1), (2), (3), (2)] é obtida da seguinte forma: 1+no+no{\ displaystyle 1 + a + a}

S{\ displaystyle S} S+S{\ displaystyle S + S} ((1) aplicado a S) S+S+S{\ displaystyle S + S + S} ((1) aplicado ao segundo S) S+no+S{\ displaystyle S + a + S} ((2) aplicado ao segundo S) 1+no+S{\ displaystyle 1 + a + S} ((3) aplicado ao primeiro S) 1+no+no{\ displaystyle 1 + a + a} ((2) aplicado a S)

nesta derivação, os caracteres não terminais são substituídos em nenhuma ordem específica.

Para obter um bypass esquerdo, sempre substituímos o não terminal mais à esquerda. A derivação esquerda da string "   " é, portanto, obtida desta forma: 1+no+no{\ displaystyle 1 + a + a}

S{\ displaystyle S} S+S{\ displaystyle S + S} ((1) aplicado a S) 1+S{\ displaystyle 1 + S} ((3) aplicado ao primeiro S) 1+S+S{\ displaystyle 1 + S + S} ((1) aplicado a S) 1+no+S{\ displaystyle 1 + a + S} ((2) aplicado ao primeiro S) 1+no+no{\ displaystyle 1 + a + a} ((2) aplicado a S)

que dá a lista [(1), (3), (1), (2), (2)].

Da mesma forma, uma derivação certa é a lista de regras usadas ao substituir sistematicamente o não terminal mais à direita primeiro. No exemplo anterior, uma derivada certa é [(1), (2), (1), (2), (3)], obtida desta forma:

S{\ displaystyle S} S+S{\ displaystyle S + S} ((1) aplicado a S) S+no{\ displaystyle S + a} ((2) aplicado ao último S) S+S+no{\ displaystyle S + S + a} ((1) aplicado a S) S+no+no{\ displaystyle S + a + a} ((2) aplicado ao último S) 1+no+no{\ displaystyle 1 + a + a} ((3) aplicado ao primeiro S)

A distinção entre derivação esquerda e direita é importante na prática porque permite, na maioria dos analisadores, levar em consideração as prioridades das operações. Os analisadores LL produzem derivações à esquerda, e os analisadores LR ramificações retas (na verdade, reduções, isto é, determinam primeiro a última regra aplicada).

Uma derivação também impõe uma estrutura hierárquica da cadeia derivada.

{{{1} S + {a} S } S + {a} S } S

onde {...} S indica uma substring reconhecida como pertencente a S. Esta hierarquia também pode ser vista como uma árvore:

S /|\ / | \ / | \ S + S | /|\ | / | \ 1 S + S | | a a

Essa árvore é chamada de árvore de derivação , análise de árvore ou árvore de sintaxe concreta (em oposição à árvore de sintaxe abstrata ) da string. O ramo esquerdo mostrado acima e o ramo direito definem o mesmo eixo do ramo. Isso é normal porque as duas derivações são duas jornadas de profundidade da árvore derivada, a primeira obtida escolhendo o nó mais à esquerda, a segunda escolhendo o nó mais à direita. Existe uma bijeção entre as derivações esquerdas e as derivações direitas.

Uma gramática é ambígua quando pelo menos uma palavra gerada pela gramática tem pelo menos duas árvores de análise separada, caso contrário, é uma gramática inambiguë ou inequívoca . Uma linguagem é inequívoca ou inequívoca se tiver uma gramática inequívoca. É denominado inerentemente ambíguo se todas as gramáticas que o geram forem ambíguas.

Um exemplo de linguagem inerentemente ambígua é a linguagem:

{nonãobnãovsm∣não,m≥0}∪{nonãobmvsm∣não,m≥0}{\ displaystyle \ {a ^ {n} b ^ {n} c ^ {m} \ mid n, m \ geq 0 \} \ cup \ {a ^ {n} b ^ {m} c ^ {m} \ mid n, m \ geq 0 \}}

Em todas as gramáticas, as palavras têm duas derivações distintas. A prova é feita por meio do lema de Ogden . nonãobnãovsnão{\ displaystyle a ^ {n} b ^ {n} c ^ {n}}

Na análise sintática de palavras geradas por uma gramática ambígua, devem ser utilizadas técnicas de análise não determinísticas e / ou técnicas adaptadas ( retrocesso , regras de desambiguação, ...)

Formas normais

Uma linguagem algébrica pode ser gerada por gramáticas algébricas de várias formas. Duas gramáticas são consideradas equivalentes quando geram a mesma linguagem.

Gramática reduzida e limpa

• Uma gramática reduzida é uma gramática onde toda variável é útil, isto é, aparece em pelo menos uma derivação de uma palavra da língua. Sempre podemos reduzir uma gramática, ou seja, remover, efetivamente, variáveis ​​desnecessárias.
• Uma gramática é apropriada quando nenhum membro da regra certa é igual à palavra vazia ou a uma variável. Podemos fazer uma gramática limpa, desde que a linguagem gerada não contenha a palavra vazia, ou então permitir a única regra , onde está o axioma, com a condição adicional de que nenhum membro da regra à direita apareça.ε{\ displaystyle \ varepsilon}S→ε{\ displaystyle S \ to \ varepsilon}S{\ displaystyle S}S{\ displaystyle S}

Forma normal de Chomsky

Uma gramática está na forma normal de Chomsky se todas as suas regras forem de uma das formas

• X→YZ{\ displaystyle X \ a YZ}
• X→no{\ displaystyle X \ para a},

onde estão variáveis ​​e é uma letra. Se o idioma gerado contém a palavra vazia, adicionamos a regra X,Y,Z{\ displaystyle X, Y, Z}no{\ displaystyle a}

• S→ε{\ displaystyle S \ to \ varepsilon},

onde está o axioma. S{\ displaystyle S}

Qualquer gramática pode estar na forma normal de Chomsky. Esta forma normal é usada, por exemplo, na definição de um algoritmo de análise , o algoritmo CYK , que decide em tempo polinomial , se uma palavra está na linguagem gerada por esta gramática.

Forma normal de Greibach

Uma gramática está na forma normal de Greibach se os membros certos de todas as suas regras começam com uma letra e são possivelmente seguidos apenas por variáveis, formalmente

X→noY1⋯Yk{\ displaystyle X \ a aY_ {1} \ cdots Y_ {k}}
X→b{\ displaystyle X \ a b}

onde estão variáveis ​​e são letras. Por exemplo, gramática X,Y1,...,Yk{\ displaystyle X, Y_ {1}, \ ldots, Y_ {k}}no,b{\ displaystyle a, b}

S→noSS∣b{\ displaystyle S \ para aSS \ mid b}

que gera a linguagem de Lukasiewicz está na forma normal de Greibach. A forma quadrática de Greibach também impõe que haja no máximo duas variáveis ​​em cada membro da regra à direita (o que é o caso aqui). Qualquer gramática pode ser colocada em uma forma quadrática de Greibach, até a palavra vazia.

Forma normal bilateral de Greibach

A forma normal bilateral de Greibach é uma forma bilateral da forma normal de Greibach: os membros certos das regras são letras terminais ou começam e terminam com letras terminais e contêm apenas variáveis ​​entre elas. Todas as regras são do formulário

X→noY1⋯Ykb{\ displaystyle X \ a aY_ {1} \ cdots Y_ {k} b}
X→vs{\ displaystyle X \ a c}

onde estão variáveis ​​e são letras. Qualquer gramática pode ser colocada na forma normal bilateral, e podemos até assumi-la na forma quadrática , ou seja, nestas regras. X,Y1,...,Yk{\ displaystyle X, Y_ {1}, \ ldots, Y_ {k}}no,b,vs{\ displaystyle a, b, c}k≤2{\ displaystyle k \ leq 2}

Gramáticas estendidas

Encontramos, especialmente em aplicativos, uma forma de gramáticas estendidas: os membros certos das regras podem ser expressões regulares. Isso ocorre na forma normal de Backus estendido . Mais precisamente, denotemos o conjunto de membros direitos das regras cujo membro esquerdo é . P(X){\ displaystyle P (X)}X{\ displaystyle X}

• Na definição usual de gramáticas algébricas, os conjuntos são finitos para qualquer variável .P(X){\ displaystyle P (X)}X{\ displaystyle X}
• Em gramáticas estendidas, conjuntos são linguagens racionais dadas por expressões regulares .P(X){\ displaystyle P (X)}
• Em uma generalização dessas gramáticas, os conjuntos são, eles próprios, linguagens algébricas .P(X){\ displaystyle P (X)}

Podemos mostrar que as duas extensões de gramáticas sempre geram linguagens algébricas.

Análise de sintaxe

Gramáticas algébricas são simples o suficiente para permitir a criação de analisadores eficientes (ao contrário das gramáticas contextuais ) em tempo polinomial no tamanho da gramática e no comprimento da palavra a ser analisada. A tarefa de tal analisador é determinar, para uma determinada palavra, se e como ela pode ser gerada a partir da gramática. O algoritmo CYK e o analisador Earley são exemplos de tais algoritmos. Os analisadores LR e LL parsers operam em tempo linear no comprimento da palavra a ser analisada e são usados ​​na prática. Por outro lado, eles apenas permitem a análise de famílias mais restritivas de gramáticas algébricas.

Notas

1. Idioma na Índia .
2. Este resultado não é bem conhecido. Foi comprovado por G. Hotz. Uma prova é fornecida em: Joost Engelfriet , “  Uma prova elementar da forma normal dupla de Greibach  ”, Information Processing Letters , vol.  44, n o  21992, p.  291-293. Uma prova e um exemplo detalhado também são dados em Autebert, Berstel Boasson (1997) .

Bibliografia

Por sua natureza fundamental, muitos trabalhos teóricos de computador contêm pelo menos uma seção sobre gramáticas algébricas. Vários livros também foram traduzidos para o francês.

Livros em francês

• Alfred Aho, Monica Lam, Ravi Sethi e Jeffrey Ullman ( trad.  Do inglês), Compilers: Principles, Techniques and Tools: With more than 200 years , Paris, Pearson,2007, 2 nd  ed. , 928  p. ( ISBN  978-2-7440-7037-2 e 2744070378 )
• Pierre Wolper , Introdução à calculabilidade: cursos e exercícios corrigidos , Paris, Dunod,2006, 3 e  ed. , 224  p. ( ISBN  2-10-049981-5 ).
• Jean-Michel Autebert, línguas algébricas , Masson,1987, 278  p. ( ISBN  978-2-225-81087-9 )
• Jean-Michel Autebert e Luc Boasson, Rational transductions: Application to Algebraic Languages , Masson,1988( ISBN  978-2-225-81504-1 )
• Olivier Carton , linguagens formais, computabilidade e complexidade ,2008[ detalhe da edição ] ( leia online )
• Jean-Michel Autebert, Jean Berstel e Luc Boasson, “Linguagens livres de contexto e autômatos pushdown” , em G. Rozenberg, A. Salomaa (editores), Handbook of Formal Languages , vol.  1: palavra, idioma, gramática , Springer Verlag,1997( ISBN  978-3540604204 ) , p.  111-174

Livro em alemão

• (de) Katrin Erk e Lutz Priese, Theoretische Informatik: eine umfassende Einführung , Berlin, Springer,2008, 485  p. ( ISBN  978-3-540-76319-2 , OCLC  244015158 ).

Livros em ingles

• (pt) Seymour Ginsburg, The Mathematical Theory of Context Free Languages , McGraw-Hill,1966, ix + 232  p. - O primeiro livro sobre linguagens algébricas.
• (pt) Alfred V. Aho e Jeffrey D. Ullman, A teoria da análise, tradução e compilação , vol.  1: Parsing , Englewood Cliffs, NJ, Prentice-Hall,1972, xii + 543  pág. ( ISBN  0-13-914556-7 )
• (pt) Alfred V. Aho e Jeffrey D. Ullman, A teoria da análise, tradução e compilação , vol.  2: Compilação , Englewood Cliffs, NJ, Prentice-Hall,1973, xii + 460  pág. ( ISBN  0-13-914564-8 )
• (pt) Michael A. Harrison, Introdução à Teoria da Linguagem Formal , Leitura, Mass., Addison-Wesley,1978, 594  p. ( ISBN  0-201-02955-3 , OCLC  266962302 ).
• (pt) John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, Introdução à Teoria dos Autômatos, Linguagens e Computação , Addison Wesley,2001, 2 nd  ed. , 521  p. ( ISBN  978-0-201-44124-6 e 0201441241 ).
• (pt) Peter Linz, Uma Introdução às Linguagens Formais e Autômatos , Jones & Bartlett Learning,2001, 410  p. ( ISBN  978-0-7637-1422-2 e 0763714224 , leia online ).

Aulas

• Anca Muscholl, "  linguagem livre de contexto  "
• Jean-François Perrot, "  Gramáticas livres de contexto e a hierarquia de Chomsky  "
• Jean Privat, "  Gramáticas não contextuais  "
• Jacques Désarménien, "  Gramáticas não contextuais  "

Veja também

• Parser packrat
• Recursão à esquerda
• Forma normal de Greibach
• Forma normal de Chomsky
• Análise LL , gramática LL
• Algoritmo CYK

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">