0

I'm trying to understand the difference between terminal and non-terminal values in a real language. I wasn't able to find enough examples on real language CFGs on the internet, most examples are abstract. Assume we have the following

int main(){
   int a = 5;
   return a + 6;
}

Are the following statements true?

Terminals: int, (, ), {, }, 5, return, +, 6, ;

Non-terminals: main, a

  • recommended reading: Open letter to students with homework problems "If your question... is just a copy paste of homework problem, expect it to be downvoted, closed, and deleted - potentially in quite short order." – gnat Oct 8 '18 at 15:44
  • All of those, including "main" and "a" are terminals. Terminals are the tokens in the language. – JacquesB Oct 8 '18 at 15:59
  • so int a = 5;return a + 6;, which is the content of the function is non terminal correct? – Josh t Oct 8 '18 at 16:04
  • 2
    Terminals and non-terminals are the parts of the language grammar. So for example a return statement might be defined in the grammar as ReturnStatement :: "return" Expression ";". The return-keyword and the semicolon are terminals, but Expression is a non-terminal. But if you look at the actual code, everything is terminals. – JacquesB Oct 8 '18 at 16:06
  • It may also be worth noting that C can't be parsed using a context-free grammar. There are cases where the parsing depends on the semantics. – David Thornley Oct 8 '18 at 16:23
3

Terminal and non-terminal symbols are an aspect of a grammar, not of a language. In a BNF grammar (which describes a context-free language), the nonterminals are the symbols “on the left”.

For example, a simple C-ish grammar might be (using BNF + regex-like quantifiers):

<program> ::= <function>*
<function> ::= <type> <identifier> '(' ')' <block>
<block> ::= '{' <statement>* '}'
<statement> ::= <statement_define>
<statement> ::= <statement_return>
<statement_return> ::= 'return' <expr> ';'
<statement_define> ::= <type> <identifier> '=' <expr> ';'
<expr> ::= <expr> '+' <term>
<expr> ::= <term>
<term> ::= <identifier>
<term> ::= <literal>

As defined, the symbols program, function, block, statement, statement_return, statement_define, expr, and term are non-terminals. They can be substituted by their right-hand side. In contrast, the symbols type, identifier, (, ), {, }, return, ;, +, and literal are terminals because they are not defined in the grammar. They form the “alphabet” that this grammar operates on.

In practice the above grammar is incomplete because some symbols have not been defined, so a separate parser (called a tokenizer, scanner, or lexer) would be responsible for recognizing them.

A grammar can be used to describe the structure of a given input. For example, a tokenizer might turn your source code into a token stream

type:int, identifier:main, (, ), {,
  type:int, identifier:a, =, literal:5, ;,
  return, identifier:a, +, literal:6, ;,
}

which the parser would turn into an abstract syntax tree based on the grammar. Here:

program
+ function
  + type: int
  + identifier: main
  + '('
  + ')'
  + block
    + '{'
    + statement
      + statement_define
        + type: int
        + identifier: a
        + '='
        + expr
          + term
            + literal: 5
        + ';'
      + statement_return
        + 'return'
        + expr
          + term
            + identifier: a
          + '+'
          + term
            + literal: 6
        + ';'
    + '}'

We can also use the grammar to generate source code, by substituting non-terminal symbols. For example:

<program>

<function>

<type> <identifier> ( ) <block>

<type> <identifier> ( ) { <statement>* }

<type> <identifier> ( ) { <statement_return> }

<type> <identifier> ( ) { return <expr>; }

<type> <identifier> ( ) { return <term>; }

<type> <identifier> ( ) { return <literal>; }

At that point no non-terminal symbols (as defined by the grammar) remain.

1

Terminal symbols are all the symbols that can appear directly in the language.

In your case you can observe int, (, ), {, }, 5, return, +, 6, ;, =, main, and a.

Non-terminal symbols are all the intermediate symbols used in the definition of the grammar rules, that will be derived further until completely replaced by terminal symbols. It's abstract grammatical constructs of the language.

In your case, and using the grammar of appendix A of K&R, it is: program, external-definition, function-definition, type-specifier, function-declarator, function-body, declarator, parameter-list, identifier, type-decl-list, function-statement, declaration-list, statement-list, statement, declaration, initializer, expression, lvalue, primary, constant, binop, and *asgnop (I think I missed some, but I hope you'll got the logic).

A context free grammar, is a grammar in which all the production rules have the form X -> Y where X is a non-terminal, and Y is a non empty group of terminals and non-terminals.

  • Your description of a context free grammar is incomplete. It has the additional constraint that the production rules that get used for a sequence of terminals doesn't depend on what has been parsed before. i.e., the meaning of a piece of code only depends on the structure and not on what has been parsed before it. – Bart van Ingen Schenau Oct 8 '18 at 19:19
  • @BartvanIngenSchenau i'm pretty sure that this property can be deduced from this definition (I've cross checked the definition with my very old textbook) – Christophe Oct 8 '18 at 19:35
  • The grammar for the C language follows your definition, but it is not context free. The meaning of a*b; depends on whether a names a type or not and that can depend on an earlier typedef declaration. – Bart van Ingen Schenau Oct 8 '18 at 20:07
  • @BartvanIngenSchenau I didn't make the definitions. My definition is equivalent to this one. The fact that there are ambiguities in the parsing because several production rules (e.g. decl-specifiers->...-> identifier*identifier-> mytype*b and expression->...->identifier*identifier->a*b) could lead to the same sequence of terminals, doesn't change that the grammar itself is context free. Context free is an attribute of a particular grammar, not of the language itself. – Christophe Oct 8 '18 at 21:45
  • I stand corrected. It turns out that I misremembered and the C language is not context free because you have to apply additional rules next to the context free grammar that is defined for it. – Bart van Ingen Schenau Oct 9 '18 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.