Headline

A kind of grammar used, for example, for syntax definition

Illustration

Context-free grammars consist of:

  • a set of terminal ("strings" from which to compose inputs),
  • a set of nonterminal (placeholders for syntactical categories in derivations),
  • an (optional) designated startsymbol (a nonterminal from which to start derivations), and
  • a set of productions (rules) for derivations.
In fact, a context-free grammar can be described just by the rules as these rules enumerate the terminals and nonterminals as well. (We may also assume that the left-hand side nonterminal of the first rule is simply the startsymbol). What's important is the structure of rules. Each rules consists of:
  • a left-hand side which is a nonterminal, and
  • a right-hand side which is some expression over terminals and nonterminals.
In the most basic form, said expressions are simply sequences over terminals and nonterminals. Alternatives for derivation are already expressible, as there could be multiple rules with the same left-hand side nonterminal. In practice, notational extensions are commonplace. For example, so-called EBNF notations may cater for these expression forms:

  • x*: Any number of repetitiions of x including 0 repetitions.
  • x?: Any number of repetitiions of x excluding 0 repetitions.
  • x|y: x or y.
  • x?: x or the empty string.
Here is a context-free grammar for a possible concrete syntax for companies of the @system; for what it matters, we use Technology:ANTLR's EBNF-like notation:

Nonterminals (with explanation):

  • Company: complete company structures
  • Department: department sub-structures of companies
  • Employee: employee sub-structures of departments
  • NonManager: managers rather than non-managerial employees
  • QString: double-quoted strings for names and addresses
  • Number: floating point numbers for salaries
Terminals:
  • "company"
  • "department"
  • "employee"
  • "manager"
  • "address"
  • "salary"
  • "{"
  • "}"
Startsymbol: Company

Productions:

Company :  
  'company' QString '{'
    Department* 
  '}';

Department :
  'department' QString '{' 
    'manager' Employee    
    Department* 
    NonManager* 
  '}';

NonManager : 'employee' Employee;

Employee : QString '{' 
    'address' QString
    'salary' Number 
  '}';

As an exercise, let us define about the same syntax with a different grammar. In the original grammar, the lists of departments and employees were separated. We may also consider a mixed list of departments and employees. To this end, we assume an extra nonterminal "SubUnit" for a choice between department and employee. As a result, we would need these alternative productions:

Company :  
  'company' QString '{'
    Department* 
  '}';

Department :
  'department' QString '{' 
    'manager' Employee    
    SubUnit* 
  '}';

SubUnit : NonManager | Department ;

NonManager : 'employee' Employee;

Employee : QString '{' 
    'address' QString
    'salary' Number 
  '}';

A (context-free) grammar has a simple semantics. It defines a set of strings (the so-called language generated by the grammar) which are derivable by repeated rule application starting from the symbol such that nonterminals are replaced by matching right-hand sides until no nonterminals are left. This generative definition also gives rise to an algorithmic problem, the parsing problem, such that one can check whether a given string is actually in the language generated by a grammar and recover the underlying syntactical structure as parse tree.


Ralf Lämmel edited this article at Wed, 03 May 2017 22:02:57 +0200
Compare revisions Compare revisions

User contributions

    This user never has never made submissions.

    User edits

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.