An introduction to parsing context-free language
Nguyen, Phuc (2020)
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-202005138807
https://urn.fi/URN:NBN:fi:amk-202005138807
Tiivistelmä
Context-free grammar is a fundamental tool in software technologies. It is present in almost all aspects of software developments, from construction of software in programming languages and compilers to applications such as data transmission, storage and presentation. This thesis aims to introduce context-free grammar and parsing context-free language to beginners by answering three questions – what context-free grammars are, what parsing context-free language means and how to parse context-free languages.
The motivation for context-free grammar is shown through its ordinary usages in daily signs, forms and numerical formulae. Having established that context-free grammar is used to describe structured information, its ability to do so is showcased further through examples in numerical expressions and programming languages.
Concrete examples and detailed illustrations are provided to show what parsing context-free language means and how to do so. To complete the introduction to parsing context-free lan-guage, an example parsing algorithm is provided. The algorithm is constructed on the idea of simulating left-most reduction on an input string and its implementation is based on a procedure called the DK-test, which is meant for determining if a context-free grammar is deterministic. This example parsing algorithm is rudimentary and limited in power, but it incorporates ideas adaptable to more advanced parsing algorithms, making it an ideal starting point for the study of parsing context-free languages.
The motivation for context-free grammar is shown through its ordinary usages in daily signs, forms and numerical formulae. Having established that context-free grammar is used to describe structured information, its ability to do so is showcased further through examples in numerical expressions and programming languages.
Concrete examples and detailed illustrations are provided to show what parsing context-free language means and how to do so. To complete the introduction to parsing context-free lan-guage, an example parsing algorithm is provided. The algorithm is constructed on the idea of simulating left-most reduction on an input string and its implementation is based on a procedure called the DK-test, which is meant for determining if a context-free grammar is deterministic. This example parsing algorithm is rudimentary and limited in power, but it incorporates ideas adaptable to more advanced parsing algorithms, making it an ideal starting point for the study of parsing context-free languages.