Chapter 2
Formal Languages and Grammars
[If] one combines the words “to write-while-not-writing”: for then it means, that he has the power to write and not to write at once; whereas if one does not combine them, it means that when he is not writing he has the power to write.
—Aristotle, Sophistical Refutations, Book I, Part 4
Never odd or even
Is it crazy how saying sentences backwards creates backwards sentences saying how crazy it is
IN this chapter, we discuss the constructs (e.g., regular expressions and context-free grammars) for defining programming languages and explore their capabilities and limitations. Regular expressions can denote the lexemes of programming languages (e.g., an identifier), but not the higher-order syntactic structures (e.g., expressions and statements) of programming languages. In other words, regular expressions can denote identifiers and other lexemes while context-free grammars can capture the rules for a valid expression or statement. Neither can capture the rule that a variable must be declared before it is used. Context-free grammars are integral to both the definition and implementation of programming languages.