It turns out that if we could just build this chart correctly--
and that's not going to be easy, but it's going to within our power--
then we've solved parsing.
Let's say that our grammar has some special start symbol S.
So goes to E, and then E could be many things.
The state we really want to be in is this one.
I have seen everything. S goes to E, and there's nothing more. We are totally done.
I mentioned before that we have to augment all of our parse states with this starting add information.
Just to be a little more specific, I have seen S goes to E,
and there was no additional previous information.
Starting from zero tokens of input,
I have seen enough to make the judgement S goes to E based on this input string.
So if the input is T tokens long, we just look to see if S goes to E dot starting at zero
is in chart T.
If it is, our input is in the language of the grammar.
If it's not, our input is not.
Parsing totally solved assuming we can build the chart,
but building the chart is going to be tricky--tricky but possible.
簡単ではありませんが
この表を正しく構築できればそれが力になり
構文解析が解けることが分かりました
特別な開始記号Sを持つ文法とします
SはEに書き換えられ
Eはいろいろなものに書き換えられます
到達したい状態はこれです
すべてを読んでSがEになる
それでおしまいです
構文解析の状態には
開始位置の情報も必要でしたね
厳密にはSがEに書き換わったものを読み
それ以前には何も読んでいませんでした
入力のうち0個のトークンを読んだ状態から
始めています
SがEに書き換えられたと判断するのに
十分な入力を読みました
入力がT個のトークンだとすると
0番目から開始してS->E・となるかどうかは
chart[T]を見れば分かります
もしあれば
入力は文法の言語に含まれる文です
そうでなければ
入力は文法の言語に含まれていません
表を書ければ構文解析は解けますが
表を構成するのは複雑です
しかし不可能ではありません
Se pudermos construir esta tabela corretamente --
e isso não vai ser fácil, mas seremos capazes disso --
entào resolvemos o problema de parsing.
Suponha que nossa gramática tem um símbolo inicial S;
S -> E, e E pode produzir várias coisas.
O estado em que queremos estar é este aqui:
eu já vi tudo -- S -> E • e não há mais nada na entrada -- terminamos completamente.
E disse antes que temos que aumentar nosso estado do parser, adicionando esssa informação de início.
Apenas para ser um pouco mais específico, eu vi S -> E •,
e não havia nenhuma informação adicional antes.
Começando de 0 tokens na entrada,
eu vi o suficiente para construir o julgamente S -> E com base nesse string de entrada.
Portanto se a entrada tem comprimento igual a T tokens, apenas temos que verificar se S -> E •, começando de 0,
ocorre na posição T da tabela.
Se ocorre, nossa entrada está na linguagem da gramática.
Se não, nossa entrada não está.
O problema de parsing fica totalmente resolvido, supondo-se que podemos construir a tabela.
Mas, construir a tabela será um pouco difícil -- difícil, mas possível.