• Home
• • Language definition
  • BNF
  • Chomsky Grammar
  • Context-sensitive and free Languages
  Formal Languages
• • Top-down parsing
  • Grammatical rules 1 and 2
  • Left recursion removal
  • Grammar ambiguity
  Syntax Analysis 
• Applet
• Program
• • Contact
  • References.html
  Contact & references 
• 
• 

The program’s capabilities:

The practical realization of grammar parsing in BNF notation was performed using a computer program written in VC++ environment. The program allows to find first and follow symbols, check the correctness of grammar and perform its presumptive revision in case left-recursion or factoring occur.

Instructions:

In the first stage of parsing, the input grammar is entered into the parser in the form of a string. Its task is to check the compatibility of this grammar’s description with BNF notation. In the case an incompatibility is found, further analysis is aborted and a message informing about the event is generated. This module was designed using FLEX and BISON tools. In the next stage, first and follow symbols are determined for the input grammar. Then, its correctness is checked. Should left recursion and/or factoring be found, in the case of left recursion, it is removed, and in the case of left-factoring, a common factor is extracted and an additional production is generated. For the revised grammar, first and follow symbols are additionally determined. In the last stage, results of the analysis are placed in the graphic interface window. This interface allows to enter the input grammar from file or from keyboard. The program has three editing windows, however, only one of them allows user modification (the first field on the left), the remaining ones are read-only. In the editing field with an option for entering text, grammar can be entered manually or loaded from file. The central field is used to display revised grammar as well as the first and follow symbols relevent to it, whereas in the last field (first field on the right) first and follow symbols relevant to the entered input grammar are displayed. After entering the last production, the ENTER key has to be pressed, which will allow to move on to the next line. The number of text lines must be at least 1 time bigger than the number of the productions entered because the parser indentifies the end of a given production based on the end-of-line marker.