10.2. Reconhecimento e Análise de Linguagens Livres de Contexto🔗
namespaceParsing
Uma gramática pode gerar palavras sobre um alfabeto de caracteres ou
sentenças sobre um alfabeto de palavras ou tokens. Dada uma sequência,
podemos usar a gramática para responder a duas perguntas.
Chamamos de reconhecimento o procedimento que responde se a
sequência pertence à linguagem gerada pela gramática. Na análise,
ou parsing, a resposta consiste nas árvores sintáticas que
representam as derivações da sequência.
Vamos usar como exemplo a gramática abaixo, que gera os palíndromos
sobre {a, b, c}. Um palíndromo é uma palavra igual à que obtemos
ao invertê-la.
Uma regra de uma gramática livre de contexto tem um único não terminal
à esquerda. Para testar uma regra com n símbolos à direita, dividimos
a entrada em n pedaços consecutivos, de todos os modos possíveis.
Para cada divisão, testamos se cada símbolo gera o pedaço que lhe
corresponde.
A função split2 enumera as divisões em dois pedaços. Para a lista
vazia, ela produz uma só divisão, com dois pedaços vazios. Para uma
lista não vazia, a primeira divisão é o pedaço vazio seguido da lista
inteira. As demais divisões são obtidas dividindo a cauda e recolocando
o primeiro elemento no primeiro pedaço.
O exemplo usa "Jan".toList para obter os caracteres e String.ofList
para exibir os pedaços como textos.
A função splitN n generaliza esse procedimento. Em zero pedaços, só a lista
vazia pode ser dividida, e há uma única divisão. Em um pedaço, a única
divisão tem a lista inteira como único pedaço. Para dois ou mais pedaços,
a função usa split2 para separar o primeiro e divide recursivamente
o restante.
A
::=
ε
|
a
|
b
|
c
|
aAa
|
bAb
|
cAc
defsplit2{α:Type}:Listα→List(Listα×Listα)|[]=>[([],[])]|x::xs=>([],x::xs)::(split2xs).mapfun(ys,zs)=>(x::ys,zs)[("","Jan"),("J","an"),("Ja","n"),("Jan","")]#evalsplit2"Jan".toList|>.mapλ(a,b)↦(String.ofLista,String.ofListb)defsplitN{α:Type}:Nat→Listα→List(List(Listα))|0,[]=>[[]]|0,Variable name `a` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_aNote: This linter can be disabled with `set_option linter.unusedVariables false`a::Variable name `as` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_asNote: This linter can be disabled with `set_option linter.unusedVariables false`as=>[]|1,xs=>[[xs]]|n+2,xs=>(split2xs).flatMapfun(ys,zs)=>(splitN(n+1)zs).mapfunrs=>ys::rs[["","","Jan"],["","J","an"],["","Ja","n"],["","Jan",""],["J","","an"],["J","a","n"],["J","an",""],["Ja","","n"],["Ja","n",""],["Jan","",""]]#evalsplitN3"Jan".toList|>.mapλxs=>xs.mapString.ofList
O reconhecedor aceita diretamente as palavras geradas pelas regras
A → ε, A → a, A → b e A → c. Para testar A → a A a,
ele procura, entre as divisões de splitN 3 xs, uma que tenha
['a'] nas duas pontas. Se encontrar uma divisão assim, testa
recursivamente se o pedaço do meio é um palíndromo. As regras
A → b A b e A → c A c seguem o mesmo procedimento.
Na primeira tentativa, recognize₀, o padrão
[['a'], ys, ['a']] identifica o pedaço central, mas não carrega a
informação de que a divisão veio de splitN 3 xs. O Lean precisa
dessa informação para verificar que a chamada sobre ys termina.
A definição de recognize usa List.attach para associar
cada divisão a uma prova de que ela pertence à lista de divisões.
A cláusula termination_by xs.length indica que a medida usada
para justificar a recursão é o comprimento da entrada. A cláusula
decreasing_by fornece a prova de que a medida diminui em cada
chamada. O lema flatten_of_mem_splitN, no bloco de detalhes,
mostra que concatenar os pedaços recupera a entrada. Aplicamos
List.length à igualdade com congrArg. Como os dois
pedaços externos têm um elemento cada, o pedaço central tem dois
elementos a menos do que a entrada.
O mesmo raciocínio explica quando o método funciona para uma regra
recursiva à esquerda, como V → V T. Se o pedaço de T tiver ao
menos um símbolo, o pedaço de V é menor que a entrada. Se o pedaço
de T for vazio, uma chamada para V sobre o primeiro pedaço
receberá a entrada inteira. Podemos descartar essa divisão quando
T não gera a palavra vazia. Em uma gramática que permite essa
derivação, descartá-la sem outro tratamento pode perder análises.
As divisões juntam-se de volta na entradatheoremappend_of_mem_split2{α:Type}:∀{xs:Listα}{p:Listα×Listα},p∈split2xs→p.1++p.2=xsα:Typep:Listα×Listαh:p∈split2[]⊢ p.fst++p.snd=[]α:Typep:Listα×Listαh:p∈split2[]⊢ p.fst++p.snd=[]α:Typep:Listα×Listαh:p=([],[])⊢ p.fst++p.snd=[]All goals completed! 🐙α:Typex:αxs:Listαp:Listα×Listαh:p∈split2(x::xs)⊢ p.fst++p.snd=x::xsα:Typex:αxs:Listαp:Listα×Listαh:p∈split2(x::xs)⊢ p.fst++p.snd=x::xsα:Typex:αxs:Listαp:Listα×Listαh:p=([],x::xs)∨∃a,a∈split2xs∧(x::a.fst,a.snd)=p⊢ p.fst++p.snd=x::xsα:Typex:αxs:Listα⊢ ([],x::xs).fst++([],x::xs).snd=x::xsα:Typex:αxs:Listαys:Listαzs:Listαh:(ys,zs)∈split2xs⊢ (x::(ys,zs).fst,(ys,zs).snd).fst++(x::(ys,zs).fst,(ys,zs).snd).snd=x::xsα:Typex:αxs:Listα⊢ ([],x::xs).fst++([],x::xs).snd=x::xsAll goals completed! 🐙α:Typex:αxs:Listαys:Listαzs:Listαh:(ys,zs)∈split2xs⊢ (x::(ys,zs).fst,(ys,zs).snd).fst++(x::(ys,zs).fst,(ys,zs).snd).snd=x::xsAll goals completed! 🐙theoremflatten_of_mem_splitN{α:Type}:∀{n:Nat}{xs:Listα}{l:List(Listα)},l∈splitNnxs→l.flatten=xsα:Typex✝:Listαl:List(Listα)h:l∈splitN1x✝⊢ l.flatten=x✝α:Typel:List(Listα)h:l∈splitN0[]⊢ l.flatten=[]α:Typex✝:Listαl:List(Listα)h:l∈splitN1x✝⊢ l.flatten=x✝α:Typex✝:Listαl:List(Listα)h:l=[x✝]⊢ l.flatten=x✝All goals completed! 🐙α:Typehead✝:αtail✝:Listαx✝:List(Listα)h:x✝∈splitN0(head✝::tail✝)⊢ x✝.flatten=head✝::tail✝α:Typehead✝:αtail✝:Listαx✝:List(Listα)h:x✝∈splitN0(head✝::tail✝)⊢ x✝.flatten=head✝::tail✝All goals completed! 🐙α:Typen:Natxs:Listαl:List(Listα)h:l∈splitN(n+2)xs⊢ l.flatten=xsα:Typen:Natxs:Listαl:List(Listα)h:l∈splitN(n+2)xs⊢ l.flatten=xsα:Typen:Natxs:Listαl:List(Listα)h:∃a,a∈split2xs∧∃a_1,a_1∈splitN(n+1)a.snd∧a.fst::a_1=l⊢ l.flatten=xsα:Typen:Natxs:Listαys:Listαzs:Listαh1:(ys,zs)∈split2xsrs:List(Listα)h2:rs∈splitN(n+1)(ys,zs).snd⊢ ((ys,zs).fst::rs).flatten=xsAll goals completed! 🐙deffail to show termination forParsing.recognize₀with errorsfailed to infer structural recursion:Cannot use parameter xs:failed to eliminate recursive applicationrecognize₀ysfailed to prove termination, possible solutions: - Use `have`-expressions to prove the remaining goals - Use `termination_by` to specify a different well-founded relation - Use `decreasing_by` to specify your own tactic for discharging this kind of goalxsys:ListChar⊢ sizeOfys<sizeOfxsrecognize₀(xs:ListChar):Bool:=xs==[]||xs==['a']||xs==['b']||xs==['c']||(splitN3xs).anyfun|[['a'],ys,['a']]=>recognize₀ys|[['b'],ys,['b']]=>recognize₀ys|[['c'],ys,['c']]=>recognize₀ys|_=>falsedefrecognize(xs:ListChar):Bool:=xs==[]||xs==['a']||xs==['b']||xs==['c']||(splitN3xs).attach.anyfun|⟨[['a'],ys,['a']],Variable name `h` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_hNote: This linter can be disabled with `set_option linter.unusedVariables false`h⟩=>recognizeys|⟨[['b'],ys,['b']],Variable name `h` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_hNote: This linter can be disabled with `set_option linter.unusedVariables false`h⟩=>recognizeys|⟨[['c'],ys,['c']],Variable name `h` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_hNote: This linter can be disabled with `set_option linter.unusedVariables false`h⟩=>recognizeys|_=>falsetermination_byxs.lengthdecreasing_byall_goalsxs:ListCharys:ListCharh:[['c'],ys,['c']]∈splitN3xsthis:[['c'],ys,['c']].flatten.length=xs.length⊢ ys.length<xs.lengthxs:ListCharys:ListCharh:[['c'],ys,['c']]∈splitN3xsthis:ys.length+1+1=xs.length⊢ ys.length<xs.lengthAll goals completed! 🐙true#evalrecognize"aabcbbcbaa".toListfalse#evalrecognize"aabcbbcba".toList
Podemos usar recognize para gerar palavras da linguagem.
Primeiro enumeramos as palavras sobre um alfabeto dado e depois
conservamos apenas as que o reconhecedor aceita.
A função generate n alphabet enumera as palavras de comprimento
n. A única palavra de comprimento zero é a lista vazia. Para
obter palavras de comprimento n + 1, a função antepõe cada
símbolo do alfabeto a cada palavra de comprimento n.
Como há palíndromos de comprimento arbitrário, fixamos um limite
para que a enumeração caiba em uma lista finita. A função
generateUpTo n alphabet reúne as palavras dos comprimentos de zero
a n. A função language filtra essa lista com recognize.
O Mathlib representa a propriedade de ser palíndromo pelo predicado
indutivo List.Palindrome. A lista vazia e as listas de um
elemento são palíndromos. Se l é um palíndromo, acrescentar o mesmo
elemento x às duas pontas produz outro, x :: (l ++ [x]). Esses
casos correspondem às regras da nossa gramática, com a diferença de
que o predicado permite qualquer elemento nas pontas.
O teorema recognize_iff_palindrome diz que recognize
concorda com esse predicado para toda palavra w sobre {a, b, c}.
Para listas, w ⊆ "abc".toList significa que cada elemento de
w pertence a "abc".toList. Essa hipótese é necessária
para garantir que todo palíndromo seja aceito. Por exemplo, xx
é um palíndromo, mas contém um símbolo fora do alfabeto do
reconhecedor.
A prova trata uma direção de cada vez, por indução em um limite para
o comprimento da palavra. Na primeira direção, cada sucesso do
reconhecedor corresponde a um dos casos de List.Palindrome.
Na segunda, a forma do palíndromo determina uma divisão que o
reconhecedor precisa testar. As equações de recognize podem
ser usadas nas duas provas porque sua terminação foi demonstrada.
Para construir as árvores que a gramática atribui a uma palavra,
seguimos as mesmas regras usadas no reconhecimento. A entrada
continua sendo uma lista de caracteres. A análise devolve uma lista
de árvores de tipo ParseTreeCharChar, com caracteres nas
folhas e o rótulo 'A' nos nós internos.
Cada uso de uma regra produz um nó. A regra A → ε produz um nó sem
filhas, e uma regra como A → a produz um nó com uma folha. Para
A → a A a, percorremos as divisões com ['a'] nas duas pontas.
Para cada árvore obtida ao analisar o pedaço central, construímos uma
árvore com essa subárvore entre duas folhas com o caractere a.
A justificativa de que a chamada recursiva recebe uma palavra menor é
a mesma usada para recognize.
O reconhecedor pode parar assim que uma regra der certo. Para analisar
a palavra, reunimos com ++ os resultados das regras e usamos
List.flatMap para reunir os resultados das divisões. Se a
palavra não pertence à linguagem, a lista de árvores é vazia. Se a
gramática atribui mais de uma árvore à palavra, a lista contém todas
elas.
defparse(xs:ListChar):List(ParseTreeCharChar):=(ifxs==[]then[.branch'A'[]]else[])++(ifxs==['a']then[.branch'A'[.leaf'a']]else[])++(ifxs==['b']then[.branch'A'[.leaf'b']]else[])++(ifxs==['c']then[.branch'A'[.leaf'c']]else[])++(splitN3xs).attach.flatMapfun|⟨[['a'],ys,['a']],Variable name `h` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_hNote: This linter can be disabled with `set_option linter.unusedVariables false`h⟩=>(parseys).mapfunt=>.branch'A'[.leaf'a',t,.leaf'a']|⟨[['b'],ys,['b']],Variable name `h` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_hNote: This linter can be disabled with `set_option linter.unusedVariables false`h⟩=>(parseys).mapfunt=>.branch'A'[.leaf'b',t,.leaf'b']|⟨[['c'],ys,['c']],Variable name `h` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_hNote: This linter can be disabled with `set_option linter.unusedVariables false`h⟩=>(parseys).mapfunt=>.branch'A'[.leaf'c',t,.leaf'c']|_=>[]termination_byxs.lengthdecreasing_byall_goalshave:=congrArgList.length(flatten_of_mem_splitNh)xs:ListCharys:ListCharh:[['c'],ys,['c']]∈splitN3xsthis:[['c'],ys,['c']].flatten.length=xs.length⊢ ys.length<xs.lengthsimpatthisxs:ListCharys:ListCharh:[['c'],ys,['c']]∈splitN3xsthis:ys.length+1+1=xs.length⊢ ys.length<xs.lengthomegaAll goals completed! 🐙[[.A ]]
#evalIO.println(parse"".toList)[]
#evalIO.println(parse"aab".toList)[[.A a [.A a [.A b] a] a]]
#evalIO.println(parse"aabaa".toList)Árvores mais enxutas
Como a gramática tem um só não terminal, poderíamos omitir o nó A
na regra A → a e devolver só a folha a. Nenhuma informação se
perderia, porque o único rótulo possível é A. Mas a árvore deixaria
de ter um nó para cada regra usada, e a correspondência entre a
gramática e o parser ficaria menos direta. Na regra A → ε nem há
essa opção pois uma árvore é uma folha ou um nó, sem o nó A, não sobra
nada para devolver. Por isso mantemos um nó para cada regra.
Exercício★★(split-nonempty)
Numa gramática sem regras com ε, nenhum pedaço da divisão pode ser vazio.
Defina split2' e splitN', que dão só as divisões sem pedaços vazios.
Confira o resultado em "Jan".