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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Context-Free Grammars and Languages

  • K. R. Chowdhary

摘要

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.