Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is `goal symbol` the same thing as `start symbol` in context-free-grammar

Tags:

Context free grammar define the four constituent parts:

  • A set of non-terminals (V)...

  • A set of tokens, known as terminal symbols (Σ)...

  • A set of productions (P)...

  • One of the non-terminals is designated as the start symbol (S); from where the production begins.

The EcmaScript specification doesn't mention start symbol, instead it mentions a goal symbol:

Starting from a sentence consisting of a single distinguished nonterminal, called the goal symbol, a given context-free grammar specifies a language, namely, the (perhaps infinite) set of possible sequences of terminal symbols that can result from repeatedly replacing any nonterminal in the sequence with a right-hand side of a production for which the nonterminal is the left-hand side.

From this definition I can probably conclude that goal symbol is actually just another name for a start symbol, but the goal symbol name is used because there are different start symbols "categories":

There are several situations where the identification of lexical input elements is sensitive to the syntactic grammar context that is consuming the input elements. This requires multiple goal symbols for the lexical grammar.

So is goal symbol is another name for start symbol in the context of CFG?

like image 484
Max Koretskyi Avatar asked Aug 28 '17 15:08

Max Koretskyi


1 Answers

Yes

What you have cited is just one definition of CFG - there are others. For example from here:

A grammar is the 4-tuple:

  1. A set of terminal symbols (i.e. the valid "words" of the language).
  2. A set of non-terminal symbols (i.e. the "parts-of-speech" of the language).
  3. A set of rules known as productions which can transform each non-terminal into a sequence of terminals.
  4. A start symbol or goal symbol, the non-terminal to generate (e.g., in English: the "sentence").

From my cursory web search, it seems that the term "goal symbol" is more often used when discussing parsers. I guess it's because there are bottom-up parsers such as LR-parsers where the algorithm does not start with the goal symbol.

Btw, the particular paragraph from the ECMAScript spec appears to be literally copied from the Java Language Specification - so you can blame anything on them :-)

like image 111
Bergi Avatar answered Sep 30 '22 15:09

Bergi