What kind of grammar does the parser use?

Question

Why?

Answer 1

The short answer is context-free (CFG) and context-sensitive (CSG).

The type of grammar required depends on the language complexity being parsed. For a very simple language, such as keywords for program options that can (optionally) occur in any order, a CFG will be adequate. The implementation can be top-down, where recognition of a keyword sets a switch if it is not already set. The parsing is very fast and error recognition is simple...either a blank-delimited phrase is or is not valid.

For a more complex language such as SQL, JCL or a programming language such as COBOL, a CSG will be used...there are reserved words which must appear in clauses within valid context. The COBOL language has (at least) sections for input/output, data and procedures to operate on either one. Files and data structures are not allowed in the procedure division and program statements are invalid in the data division.

The implementation may be bottom-up or top-down. More complex languages where the same verb means different things in different contexts present significant difficulty in grammatical error analysis. When a word or phrase is encountered in an invalid context, generation of an error message that will allow the user to correct the mistake is very important. Many times, the user does not know that they have made a mistake until the compiler or syntax checker flags it.

There are some grammar mistakes that can be given a warning and a default value assumed, such as obsolete modifiers that were allowed in a prior version of the language and are no longer valid. Ignore it and proceed to perform the purpose of the language paragraph.

If you want to learn more, take a course in compiler writing.