As the previous example suggests, we can use parentheses to control ambiguity.
Here I've taken our expression grammar from before and updated it with a new rewrite rule.
Now expression can be replaced by open parentheses, expression, close parentheses.
This should totally remind us up the P goes to open P close rule from before for balanced parentheses.
It's going to behave mostly the same way.
With this new grammar, both of these utterances--
open 1 minus 2 plus 3 and 1 minus open 2 plus 3 close--
both of them are in the language of this grammar.
However, while both of these are okay, so is this one.
It doesn't forbid the ambiguous one.
It just allows us to have more precise renditions.
We've solved some of the problem.
If we're thinking ahead, we can use parentheses, but we're still allowing ambiguous phrasing.
Here I've drawn our favorite utterance from before--1 minus 2 plus 3--
and I've written out two different parse trees for it.
This one corresponds to 1 minus 2 plus 3.
At the top level we're subtracting, and then the 2 plus 3 are grouped together.
This one corresponds to 1 minus 2 plus 3.
At the top level we're adding, and the 1 minus 2 is grouped together.
Formally, we say that a grammar is ambiguous if there is at least one string in it--
1 minus 2 plus 3 and that single string has more than one parse tree.
Here I've drawn very stylized versions of the parse trees.
If you can find even one string for which this is true,
officially the whole grammar is ambiguous.
先ほどの例のようなあいまいさを回避するためには
()を使います
今までの文法式に新しい生成規則を追加しました
expは(exp)に置き換えられます
すでに学習した
対応のとれた括弧の規則を思い出します
ほとんど同じ考え方です
この新しい文法を使うと
(1-2)+3と1-(2+3)
どちらの文もこの文法に当てはまります
その一方で最初の式もまた
正しいということになります
あいまいなものを禁止していないからです
規則によって より正確な表現が可能になりました
問題の一部を解決しましたね
()を使えば正確になりますが
ここではまだあいまいな表現が含まれています
ここに1-2+3の文を書きました
それに対して2つの異なる解析木を書きました
右の図は1-(2+3)に対応しています
上部で引き算を行い
2+3はグループ化されています
これは(1-2)+3に対応しています
上部で足し算を行い
1-2がグループ化されています
1つの文字列が複数の解析木を持つ場合
つまり1-2+3の例が成立する場合
文法はあいまいです
ここに簡略化された解析木を書きました
これが当てはまる文字列を1つでも見つけたら
文法全体があいまいということになるのです
Como o exemplo anterior sugere, podemos usar parênteses para controlar ambiguidade.
Aqui, peguei nossa gramática de expressões anterior e introduzi uma nova regra de reescrita:
exp -> ( exp ).
Isso nos lembra a regra P -> ( P ) da nossa gramática de parênteses balanceados,
e se comporta mais ou menos do mesmo modo.
Com essa nova gramática, essas duas sentenças --
`(1 - 2) + 3' e `1 - (2 + 3)' --
estão ambas na linguagem desta gramática.
Entretanto, embora ambas sejam ok, esta também é.
A gramática não evita a ambigudade,
apenas nos permite ter sentenças mais precisas.
Resolvi apenas parte do problema.
Se pensarmos bem, podemos usar parênteses, mas ainda podemos ter sentenças ambíguas.
Escrevi aqui nossa sentença de antes -- 1 - 2 + 3 --
e desenhei duas diferentes árvores de derivação para ela.
Esta corresponde a `1 - (2 + 3)'.
No topo, estamos substraindo, e depois `2 + 3' estão agrupados.
Esta outra corresponde a `(1 -2) + 3'.
No topo, estamos somando, e o `1 -2' é agrupado.
Formalmente, dizemos que a gramática é ambígua se existe pelo menos um string nela --
`1 - 2 + 3' seria esse string -- que tem mais de uma árvore de derivação.
Desenhei aqui versões bem estilizadas das árvores de derivação.
Se você puder encontrar um string para o qual isso seja verdadeiro,
oficialmente toda a gramática é ambígua.