Context-Free Grammars and Languages
摘要
The largest number of languages we study and are also in practice are context-free languages (CFLs), and the corresponding grammars are the context-free grammars (CFGs). All the high-level computer languages fall in this class. Language processing, e.g., language translation, parsing, ambiguities, and disambiguation, is immensely concerned to the study of context-free languages and grammars. This chapter is concerned with above areas. It starts with regular languages and grammars, their relation to CFLs and CFGs, left- and right-linear grammars. This is followed with closure properties of CFLs and their proofs, derivations/parsing of arithmetic expressions, and parsing of simple natural language sentences. Ambiguities in languages, their types and challenges, and disambiguation methods are presented with their theory and worked examples. The invertible grammar with its significance, and decidable properties of CFLs are also introduced. The chapter concludes with advanced grammar—the operator precedence grammar, summary, self-review questions, and number of exercises at end.