Programmer's Guide To Theory - Practical Grammar
Written by Mike James   
Wednesday, 24 January 2024
Article Index
Programmer's Guide To Theory - Practical Grammar
Extended BNF
Green Dreams
Travelling the Tree

Travelling the Tree

Now that we have said the deeply unfashionable thing that syntax is not isolated from semantics we can now see why we bother to use a grammar analyzer within a compiler.

Put simply a syntax tree or its equivalent can be used to generate the machine code or intermediate code that the expression corresponds to.

The syntax tree can be considered as a program that tells you how to evaluate the expression.

For example, a common method of generating code from a tree is to walk all its nodes using a “depth first” algorithm.

That is, visit the deepest nodes first and generate an instruction corresponding to the value or operator stored at each node. The details of how to do this vary but you can see the general idea in this diagram.

traverse

 

So now you know. We use grammar to parse expressions, to make syntax trees, to generate the code.

A Real Grammar Of Arithmetic

You might like to see what a real grammar for simple arithmetic expressions looks like:

<Exp> -> <Exp> + <Term> |<Exp> - <Term> |<Term>
<Term> -> <Term> * <Factor> | <Term> / <Factor>
| <Factor>
<Factor> -> x | y | ... |

Of course it leaves out proper variable names, operators other than  +, -, * and / but it is a reasonable start.

 

Summary

  • Grammar is not just related to the different machines that characterize the languages they describe. Grammars are generally useful in computer science.

  • The most common method of describing a grammar is some variation on BNF or Backus-Naur Form. It is important to realize that there is no standard for this, but the variations are usually easy to understand.

  • Extended BNF allows it to describe language forms that are specified as regular expressions.

  • Often syntax diagrams are easier to understand than pure BNF.

  • A grammar is often said to be to do with the syntax of a language and nothing at all to do with semantics, the meaning. This isn’t completely true.

  • To be useful, a grammar has to reveal the meaning of a language and it has to be compatible with its meaning.

  • With a suitable grammar you can work backwards from the sequence of symbols to the rules that created them. This is called parsing.

  • There are many parsing algorithms and in general simple grammars have simple parsing methods.

  • If a grammar is compatible with the meaning of a language then parsing can be used to construct a syntax tree which shows how the components group together.

  • A syntax tree can have many uses, but the main one in computer science is to generate a sequence of machine instructions that correspond to the original sequence of symbols. This is how a compiler works.

Further reading:

Assemblers and assembly language

The Heart Of A Compiler

John Backus - the Father of Fortran

Peter Naur Dies Aged 87 

Brackets are Trees

Finite state machines

Turing Machines

A Concise Introduction to Languages and Machines

Language Implementation Patterns

The Universe as a Computer

 

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

theorycover

Contents

  1. What Is Computable?
  2. Finite State Machines
  3. What is a Turing Machine? 
  4. Computational Complexity
  5. Non-computable numbers
  6. The Transfinite
  7. Axiom Of Choice
  8. Lambda Calculus
  9. Grammar and Torture
  10. Reverse Polish Notation - RPN
  11. Introduction to Boolean Logic
  12. Confronting The Unprovable - Gödel And All That
  13. The Programmer's Guide to Fractals
  14. The Programmer's Guide to Chaos*
  15. Prime Numbers And Primality Testing
  16. Cellular Automata - The How and Why
  17. Information Theory
  18. Coding Theory
  19. Kolmogorov Complexity

*To be revised

kotlin book

 

Comments




or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

<ASIN:1848001207>

<ASIN:0465030793>

<ASIN:193435645X>

<ASIN:0123745144>



Last Updated ( Wednesday, 24 January 2024 )