In this problem, we're given an input string and
the parse chart that was created from parsing that string.
And we're tasked with finding the grammar on which
that token was parsed. So let's look at the problem.
Here we have the given string, and here we
have the parse chart. Our strategy is going to go
through each line of the parse chart and look through
the rules that explicitly appear for the first time. Say,
this one right here that indicates E goes
to parenthesis E parenthesis, is explicitly in the
grammar. Add those to the grammar. Run the
parsing algorithm. And then we're going to see if
using that grammar on this token generates this
exact parse chart. So let's get started. Looking at
chart state zero, we see six rules right here. Each of these six rules has to be
in the grammar because no tokens have been read, and we're at
the beginning of each of them. So let's add those to the
grammar. Okay, here's the six rules we were given in the first
state of the parsing chart. And if we run this through our parser,
we'll see the chart that it generates is not exactly the same.
So we're missing something. Let's keep going. Here, we have the continuation of
five rules. And if you look closely, there are no new rules
here. These are all just shifts of the rules that we found in
chart state zero. The minus comes from the minus, the
plus comes form the plus, and so on. So let's
move on to chart two. Here we go. A goes
to nothing, that's new. A goes to NA, also new. And
lastly, we have the two rule, two rules for NA.
So let's put that into our grammar. If we run
this grammar in our parser with that token, we'll see
that we get the same exact chart that we were given,
meaning that we found the answer.
この問題は入力文字列と
文字列を構文解析した時に作られた表が与えられ
トークンを構文解析した文法規則を
見つけるものでした
問題を見てみましょう
これが入力文字列でこちらが構文解析の表です
問題を解く方法として
この表の各行を見て
初めて出現する規則を集めていきます
例えばこの部分はEを(E)に置き換える規則が
文法にあると明示しています
これらを文法に加えます
構文解析アルゴリズムを実行し
この文法を使って同じ構文解析の状態の表が
生成されるかを見ます
では始めましょう
chart[0]を見ると6つの規則があります
まだトークンを読み込んでいないので
それぞれの文法規則の始めにいることになります
これらの規則を文法に加えます
これがchart[0]から分かる6つの規則です
これを構文解析プログラムで実行しても
生成された表は同じになりません
何かが足りないのです 続けます
次に5つの状態が続きますが
新しい規則はありません
chart[0]にあった規則をシフトしただけです
-はこの-、+はこの+から来ていて
以下も同じです
chart[2]に移りましょう
A->・とA->・NAのどちらも新しい規則です
最後にNAに関する規則が2つあります
これらも文法に加えます
これを使って同じトークン列を構文解析すると
与えられたものと同じ表が生成されます
従ってこれが答えだと分かります