Language - (Grammar | Syntax | Lexicon)



Grammar in the context of a compiler. Ie how to define it.

See the grammar section if you are interessed on the structure.

In processing computer languages, semantic processing generally comes after syntactic processing, but in some cases semantic processing is necessary for complete syntactic analysis, and these are done together or concurrently.

Different Grammar Type

The grammar language (ie type) is dependent of the parser generator

Below is a non-exhaustive list:

See also Grammar Conversion Tool


Computer language syntax is generally distinguished into three levels:

  • Words – the lexical level, determining how characters form tokens. In a compiler, this is the lexer works to discover Words.
  • Phrases – the grammar level, narrowly speaking, determining how tokens form phrases. In a compiler, this is the parser works to discover Words.
  • Context – determining what objects or variables names refer to, if types are valid, etc. In a compiler, this is the work of the semantic analysis to add context.


How you work to define the grammar depends on your taste and knowledge of the syntax.

There is basically two ways to define the rules tree.


A bottom-up approach will:

  • start by defining the tokens
  • then create the tree by adding hierarchical relation between the token
  • until the top of the syntax is met


The Top-down approach will:

  • start with the top level
  • slice every level
  • to get to the token (the leaf of the tree)


See Grammar - Hierarchy of grammar (Chomsky)

To Code

See Grammar-to-code mappings



For example, a correct sentence always consists of a subject followed by a predicate.

This rule can be expressed with formula's that are called:

  • syntax rules,
  • syntax productions,
  • or syntactic equations.

This above sentence can be described by the following formula:

sentence = subject predicate.


  • Subject and predicate are syntactic classes

If we add to this formula the two further formulas

subject   = "John" | "Mary".
predicate = "eats" | "talks".


  • the symbol | is “or”

We define herewith exactly four possible sentences, namely

John eats         Mary eats
John talks        Mary talks

Shorthand notation

S = AB.
A = "a" | "b".
B = "c" | "d".
L = {ac, ad, bc, bd}


  • The set L of sentences which can be generated is called the language. It consists of only four sentences.

Nesting is a property particularly important in the definition of structured languages.

Graphical representation

The graphical representations are:

See What is a Railroad Diagram? known as Syntax diagram


A language is defined by the following symbol type:

Symbol Type Also Called Cardinality Definition Example
term set
These symbols are said to be terminal,
because they cannot be substituted by any other symbols.
John, Mary, eats, talks.
non-terminal identifier set They denote syntactic (classes|category) and can be substituted. Sentence, Subject and predicate
syntactic equations productions set These define the possible substitutions of non-terminal symbols.
An equation is specified for each non-terminal symbol.
start 1 This symbol is a non-terminal symbol. Sentence

Syntactic equations - Backus Naur Form (BNF), Extended BNF (EBNF) and ABNF

A language is, therefore, the set of sequences of terminal symbols which, starting with the start symbol, can be generated by repeated application of syntactic equations, that is, substitutions.

The idea of defining languages and their grammar with mathematical precision goes back to N. Chomsky. It became clear, however, that the presented, simple scheme of substitution rules was insufficient to represent the complexity of spoken languages. This remained true even after the formalisms were considerably expanded. In contrast, this work proved extremely fruitful for the theory of programming languages and mathematical formalisms. In passing, we emphasize that this rigour applied to the syntax only, not to the semantics.

The use of the Chomsky formalism is also responsible for the term programming language, because programming languages seemed to exhibit a structure similar to spoken languages. This term is rather unfortunate, because a programming language is not spoken, and therefore is not a language in the true sense of the word. Formalism or formal notation would have been more appropriate terms.

ambiguous language

The structure of a (well formed) sentence is relevant, because it is instrumental in establishing the sentence's meaning. Owing to the syntactic structure, the individual parts of the sentence and their meaning can be recognized independently, and together they yield the meaning of the whole.

expression = number | expression "+" expression.
number = "1" | "2" | "3" | "4" .

“4 + 2 + 1” is a well-formed expression. This expression may even be derived in several ways, each corresponding to a different structural trees, as shown below:

Grammar Different Structural Trees For The Same Expression

The two differing structures may also be expressed with appropriate parentheses, respectively :

  • (4 + 2) + 1 = 7
  • 4 + (2 + 1) = 7

Fortunately, thanks to the associativity of addition both yield the same value 7.

But this need not always be the case. The mere use of subtraction in place of addition yields a counter example which shows that the two differing structures also yield a different interpretation and result:

  • (4 - 2) - 1 = 1
  • 4 - (2 - 1) = 3.

The example illustrates two facts:

  • Interpretation of sentences always rests on the recognition of their syntactic structure.
  • Every sentence must have a single structure in order to be unambiguous.

We call a syntactic class ambiguous if it can be attributed several structures. A language is ambiguous if it contains at least one ambiguous syntactic class (construct).

context-free languages

Language - Context Free Grammar (CFG)


Discover More
Card Puncher Data Processing
Antlr - (Grammar|Lexicon) (g4)

Grammar in the context of Antlr. The grammar definition of Antlr is called a antlr/antlr4/blob/master/doc/lexicon.mdLexicon because the grammar is used by the lexer (hence the lexer grammar) See: ...
CSS - Grammar

grammar and lexical scanner Grammar
Card Puncher Data Processing
Code - (Programming|Computer) Language

how the language is structured (grammar), how to name things you want to talk (vocabulary), and the customary and effective ways to say everyday things (usage). ...Grammarvocabularycommunity...B00B8V09HYEffective...
Card Puncher Data Processing
Code - Grammar / Syntax (Lexical)

This section regroups the entity of a computer language from a lexical point of view. It's the same as Parts of the speech for a natural language. Grammars are useful models when designing software...
Card Puncher Data Processing
Code - Semantic (Meaning|Behaviour)

Semantic is also known as intrinsic meaning. In a programmatic language: Syntax is like having the words in a sentence in the right order. whereas Semantics is like having the sentences in a paragraph...
Card Puncher Data Processing
Computer Language

A programming language is a interface to the control of a CPU effectively controlling a computer. A language is a (possibly infinite) set of string all of which choose their symbols from some one alphabet....
Computer Language - (Compiler|Interpreter) - Language translator

Computer Language are written in plain text. However, computers interpret only particular sequence of instructions. This transformation from a plain text language to instructions is called compilation...
Concrete Syntax Tree - What is that ?

A concrete syntax tree is a tree representation of a grammar that contains the whole parsed document
Grammar Of Graphics Pipeline
Data Vizualization - Grammar of Graphics

Grammar of Graphics Data to visualize Transformation (Data Processing) - Grouping, agg, stats, projection - Represent data - scale - Function that map data value to visual value ...
Card Puncher Data Processing
Datacadamia - Data all the things

Computer science from a data perspective

Share this page:
Follow us:
Task Runner