Today I read chapters 5 of 6 of the Linz book. Chapter 5 talks about context-free languages. Context-free language is a broader set of languages which is able to represent programming languages syntaxes, as opposed to regular languages only able to represent certain tokens. Regular language is a subset of context-free language. Further, I learned about parsing and ambiguity in 5.2 and how to use derivation trees to check ambiguity.
Chapter 6 is simplification of context-free grammars and normal forms of them. To simplify a context-free grammar, there are three goals: no unit productions, no useless variables, and no λ-productions. It is proved in the book that every context-free grammar can be transformed to achieve these three goals. Then the book gives definitions for two common normal forms: Chomsky Normal Form, which has at most two variables on the right side, and Greibach Normal Form, in which all productions have the form A → ax, where a is a terminal symbol and x is a star-union of variables. According to the book, Chomsky form is helpful for testing membership. I am still a little confused with this membership-testing algorithm, but I will be able to understand it.
The next chapter is about Pushdown Automata, which is similar to Finite Automata. The relationship between FA and regular languages is similar to the relationship between Pushdown Automata and context-free languages. I will read about this in the weekend.
I also read one paper by Shaffer that introduces JSAV library on which OpenDSA project is built on. Citation and summary can be found here. There goes my first week on JFLAP. Can’t wait to start coding!
The development of online version of JFLAP depends heavily on JSAV, so it is essential for me to understand the design patterns and concepts behind JSAV. The product that I contribute to this summer should conform to the general patterns of other eTextbooks in the OpenDSA projects.