Existe uma resolução diferente para o problema do “outro pendente” que não seja “correspondência mais próxima”?

9

Os seguintes presentes gramática livre de contexto uma "pendurado outra" tipo ambigüidade (imaginar que $a$ significa if expr thene $b$ significa elsee $c$ está para algum outro tipo de instrução ou bloco):

\begin{aligned} S & \to a S b S | a S | c \end{aligned}

$\begin{aligned} S &\rightarrow aSbS \;|\; aS \;|\; c\\ \end{aligned}$ Por exemplo,

a a c b c

$aacbc$ pode ser analisado como

(a (a c b c))

$(a(acbc))$ ou como

(a (a c) b c)

$(a(ac)bc)$ (esta é a palavra ambígua mais simples / mais curta para essa gramática).

A maneira "padrão" de resolver essa ambiguidade "dangling else" força a instrução "else" ( $b$ ) a parear com o "se-então" mais próximo / mais interno ( $a$ ). Isso pode ser realizado da seguinte maneira:

\begin{aligned} S & \to a T b S | a S | c \\ T & \to a T b T | c \end{aligned}

$\begin{aligned} S &\rightarrow aTbS \;|\; aS \;|\; c\\ T &\rightarrow aTbT \;|\; c\\ \end{aligned}$ Esta gramática é inequívoca. No exemplo acima, força aanálise

(a (a c b c))

$(a(acbc))$ .

Pergunta: Existe outra maneira natural de resolver a ambiguidade que forçaria a análise de ? Em outras palavras, eu estou procurando uma gramática que gera a mesma língua que os dois acima, que é inequívoca, e que analisa como . $(a(ac)bc)$ $aacbc$ $aacbc$ $(a(ac)bc)$

Observação: Minha primeira tentativa foi a seguinte: que resolve a ambiguidade deconforme necessário - mas essa gramática ainda é ambígua:pode ser analisada comoou como.

\begin{aligned} S & \to a S b S | a U | c \\ U & \to a U | c \end{aligned}

$\begin{aligned} S &\rightarrow aSbS \;|\; aU \;|\; c\\ U &\rightarrow aU \;|\; c\\ \end{aligned}$

a a c b c

$aacbc$

a a c b a c b c

$aacbacbc$

(a (a c) b (a c b c))

$(a(ac)b(acbc))$

(a (a c b (a c)) b c)

$(a(acb(ac))bc)$

context-free formal-grammars parsers ambiguity Gro-Tsen
fonte

11

E no seu último exemplo, qual das duas análises possíveis você considera "natural" ou correta, e por quê?

Richard

@rici Sim, esta é uma pergunta complicada !, e eu não sei. Ficarei feliz com uma gramática inequívoca que produz a análise de

. O que eu mais importa é que

(com mais

é que

's) corresponde ao

-ésimo última

com o

-ésimo

(e deixa o mais interna

's incomparável).

a a c b a c b c

$aacbacbc$

a a a \dots a a a c b c b c \dots b c

$aaa\ldots aaacbcbc\ldots bc$

a

$a$

b

$b$

k

$k$

b

$b$

k

$k$

a

$a$

a

$a$

Gro-Tsen

7

Esse problema é um análogo exato do problema de correspondência entre parênteses em uma expressão na qual alguns dos parênteses próximos foram omitidos. Aqui, um "se" (ou na gramática representativa) é um parêntese aberto e um "outro" ( ) é um parêntese próximo. (A partir da sequência de e s, você pode inserir s mecanicamente colocando um antes de cada e um no final.) Como se encaixa melhor no meu cérebro entre parênteses, escrevo como se esse fosse o problema em questão. $a$ $b$ $a$ $b$ $c$ $b$

A resolução tradicional de "correspondência mais próxima" do pendente corresponde a cada fechamento com a abertura mais recente ainda sem precedentes. Isso significa que nunca existe uma abertura incomparável (ou fechada, nesse caso) entre uma abertura correspondente e seu fechamento correspondente.

Uma alternativa possível seria combinar cada fechamento com o primeiro aberto possível inigualável. "Possível" aqui significa que o espaço aberto pode ser correspondido sem violar o aninhamento entre parênteses (por exemplo, o primeiro em não pode corresponder ao último ). $($ $()()$ $)$

Essa correspondência deve ser realizada de fora para dentro, para que não seja tentada uma correspondência até que todos os pares anexos tenham sido correspondidos. Esse fato torna impossível produzir uma análise com um algoritmo de contorno limitado, uma vez que a análise precisa trabalhar para dentro de ambas as extremidades, depois de dividir a sequência em segmentos completamente correspondentes (porque eles limitam efetivamente o intervalo de correspondências potenciais).

No entanto, o fato de não existir um analisador online da esquerda para a direita não implica que não haja CFG inequívoco. (Evidentemente: uma linguagem palindrômica deve ser analisada de ambos os lados até o meio, mas é fácil escrever uma gramática inequívoca).

Para produzir uma gramática para o problema de parênteses de "correspondência mais distante", confiei no fato de que uma abertura não correspondida não pode ser seguida por uma abertura correspondente. Se fosse, a propriedade de correspondência mais distante não se aplicaria porque a abertura não correspondida poderia corresponder ao fechamento da abertura correspondida, portanto, o fato de não corresponder viola a propriedade de correspondência mais distante.

Então aqui está a gramática um pouco desajeitada:

\begin{aligned} S & \to U | M \\ U & \to T | a U b T | a U b c | a M b U \\ M & \to a M b M | c \\ T & \to a T | a c \end{aligned}

$\begin{aligned} S&\to U \;|\; M \\ U&\to T \;|\; a U b T \;|\; a U b c \;|\; a M b U \\ M&\to a M b M \;|\; c \\ T&\to a T \;|\; a c \\ \end{aligned}$

é o símbolo inicial; são declarações totalmente correspondentes; são definitivamente declarações incomparáveis (o que significa que incluem pelo menos uma inigualável , de modo que não pode estar vazio) e é uma "cauda" consistindo apenas de inigualável s. O fato acima sobre aberto incomparável pode ser lida directamente a partir da gramática: toda inigualável abre são derivados de , a só pode aparecer no final de um , e um só pode ser seguido por um . $S$ $M$ $U$ $a$ $T$ $a$ $T$ $T$ $U$ $U$ $T$

A clunkiness vem de impedir que corresponda à string vazia. Isso evita um monte do que considero ambiguidades espúrias: são espúrias no sentido de que a correspondência entre abrir e fechar é a mesma em todas as análises alternativas. Se for permitido ser nulo, ele também derivará uma sequência completamente equilibrada. Como é, na verdade, , isso leva a uma ambiguidade na qual você pode considerar um completamente equilibrado como uma série de seguida por um vazio ou menos seguida por um completamente equilibrado . $U$ $U$ $S$ $M^* U$ $S$ $M$ $U$ $M$ $U$

Provavelmente, há uma solução melhor do que a que eu escolhi. Mas este parece funcionar e funciona bem com o analisador GLR de Bison, que eu costumava testá-lo; esse analisador reclama de análises ambíguas, a menos que você escreva um código extra para lidar com a ambiguidade, e fiquei com preguiça de fazer isso. Testei-o com seqüências de até 20 fechos + abertos, e parece ter produzido uma análise inequívoca para cada sequência aninhada corretamente, sem produzir análises para sequências aninhadas incorretamente.

rici
fonte

Parabéns por conseguir o que eu concluí que era provavelmente impossível! Eu verifiquei experimentalmente que, para palavras de tamanho ≤ 16, esta gramática é realmente inequívoca e gera as mesmas palavras que as da minha pergunta. Agora eu tenho que entender em detalhes como isso funciona!

Gro-Tsen

@ Gro-Tsen: Espero que o segundo parágrafo ajude a explicar. A gramática é muito mais simples, com as ambiguidades espúrias deixadas em:

(

como na minha solução,

S \to a S b T | a M b S

$S \to aSbT \;|\; aMbS$

M

$M$

) e foi o que descobri quando estava pensando no problema. Demorei um pouco para me convencer de que era necessário fazer

ser nulo para evitar análises ambíguas (embora, como eu disse, a ambiguidade seja relativa), e um pouco mais de tempo para contornar meu desgosto pelo caminho. Eu escolhi impor isso. Aposto que há uma apresentação mais elegante.

T \to a T | c

$T\to aT\;|\;c$

U

$U$

Richard

0

Tome a + b + c + d + e abcde. Existem duas maneiras óbvias de como uma gramática pode analisá-las, mas há uma maneira que usamos.

No caso do "outro pendente", não é assim que as pessoas encaram. Em vez disso, a sintaxe é interpretada como "se", seguida por zero, um ou mais "else if", seguida por um "else" opcional.

gnasher729
fonte

a c b a c b a c b c

$acbacbacbc$

Existe uma resolução diferente para o problema do “outro pendente” que não seja “correspondência mais próxima”?

Respostas: