CODEWITHSUNDEEP
algorithmcomputer-sciencecontext-free-grammarcomputation-theory
dev_weeb
dev_weeb

Reputation: 125

Algorithm for a Context Free Grammar

I'm trying to design an algorithm that takes as input a CFG G, and a terminal symbol a, and outputs yes if S (the starting rule of G) can generate a sentential form that starts with a. i.e., if there is a string α in (T U N)* such that S =>* aα , else it outputs no. For example, if the grammar is S - > [S] | SS | ε, and if a = ], the answer is no. I'm not looking for code, I'm just trying to understand how I should approach this topic in pseudo code.

Upvotes: 3

Views: 437

Answers (2)

Gene
Gene

Reputation: 46960

There are three ways X can derive a string starting with a.

  1. There's a rule of the form X -> a...
  2. There's a rule of the form X -> A... and A derives a string starting with a.
  3. There's a rule of the form X -> B A... and B derives ε and A... derives a string starting with a.

You can use these to build an algorithm that looks at all the rules of the grammar starting with those of the form S -> ... and applies either check 1 if the rhs starts with a terminal or both checks 2 and 3 if it starts with a non-terminal. Each check corresponds to a (possibly recursive) function returning a boolean.

One interesting detail is the need to deal with cycles in the grammar, e.g. single rules like A -> A a, but also A -> B..., B -> C..., C -> A.... If you're not careful, the mutually recursive checks will recur infinitely. I'll let that to you. Think about how a depth first search avoids following cycles in a graph forever.

Another detail is how to determine if a given non-terminal B derives ε. You should be able to work that out yourself, but if all else fails, look up "nullable non-terminal." You'll find a well-known little algorithm.

If any of the checks are positive, return yes. Else exhaustive application of the rules has found no way. Return no.

Upvotes: 2

Jay Kominek
Jay Kominek

Reputation: 8783

You could run just the predictor of an Earley parser until it stops predicting, and see if it generates any rules that start with the terminal in question.

Or start from the bottom up, mark all the nonterminals that accept the terminal in question as their first input, then mark all the nonterminals which accept already marked nonterminals as their first input, and repeat until done, and see if S is in the set of marked nonterminals.

Upvotes: 2

Related Questions