The CYK Parser is really coming along now! We had a late morning meeting with Professor Rodger and discussed the work that we've done so far and her ideas for visualization of the CYK algorithm (we're still working in Model, and this delves more into View, but it's something to start thinking about). Otherwise, Ian and I spent today continuing to work on CYK and once he implemented the tracer to track which derivations would be applied to generate the string, things really started falling into place, and paved the way for extensive refactoring, code reorganization, and more detailed documentation, as well as deleting classes that will no longer be necessary. No more red X's for classes in the CYK package (for now at least) = progress!
We're now working on using threads for the CYK Parser; Julian gave us a brief overview, which I've supplemented by doing more online research/reading in addition to what I looked at last week. Other to-dos for the CYK Parser include figuring out what other information we need to be able to extract beyond the answers themselves (for example, the brute force parser and the number of nodes generated so far) and making it a steppable algorithm.
previous day | next day | return to calendar
I continued to work with Ian on the CYK Parser in the morning. Now that the parsing algorithm itself has been implemented, we focused on building the code and modifying parts of existing code to ensure it would be a steppable algorithm. In JFLAP, when users choose to implement a particular algorithm, there is the option to "step" through it one step at a time - usually by a unit increment such as processing the next letter in the input or showing the next node on a derivation tree, for example. While making the CYK parser steppable by each cell in the parse table, we also worked on making sure it conformed to the new parser hierarchy and uses various new classes or methods that Julian's been implementing for JFLAP 8.0.
This afternoon, I began re-implementing the Brute Force Parser, basically recoding from scratch. Although there doesn't seem to be any problem with the existing parser's functionality, the primary motivation for the redesign is to make sure all the parsers fit within the new parser hierarchy and makes proper use of the new classes that have been developed (and in some cases, replaced older classes, data structures, etc.). After spending some time carefully looking at the Brute Parser code, I started coding. Although I'm not finished yet, I have a good idea of how I plan to approach it and now that I've gotten properly started, I expect things will fly faster tomorrow. Also on the upcoming to-do list: Restricted and Unrestricted brute parsers
previous day | next day | return to calendar
previous day | next day | return to calendar
Today was another parsing day, this time focusing on the brute force parser. Working with Ian and Julian, we made significant progress on completing the basic step of the parsing algorithm, and are now working on optimizing the process so that it doesn't take, for example, tens of thousands of nodes to parse a five-symbol input given a reasonably succinct grammar. The existing code in JFLAP for brute parsing, dating back to its much earlier days, does a lot to test for and remove derivations that cannot yield the input, and we're working to take the existing algorithm and modify it to be inline with JFLAP 8.0 - however, its features do seem quite impressive and definitely worth keeping around. While helping Ian figure out how to break out of multiple nested loops at once, I also learned about the ability to label a loop and break out of a particular loop by its name, which I thought was really cool.
During lunch, we heard from the undergraduate research lunch series speaker for this week, Landon Cox. Currently a Professor in the Duke Computer Science department, he actually completed his undergraduate education at Duke as well! The topic of his talk was "Kahawai: Pwning Mobile Gaming through Collaborative Rendering," which talked about how GPU rendering for gaming on mobile devices could be supported by offloading part of the job to the server (rather than done on the mobile device itself). Even though I'm not an avid gamer (and don't possess a smartphone at all, for that matter), it was really interesting to hear about some of the tradeoffs including quality and bandwidth, and especially to see short video examples that helped emphasize the differences between the different approaches described. Definitely instilled a newfound appreciation for how mobile game developers need to ensure that the frames are both high-quality and rendered fairly quickly so the game doesn't look "choppy".
I continued to work with Ian on finishing up and testing the brute force parser, which is now capable of handling most strings of a reasonable length that we tested with appropriate grammars (although it could still use optimization for stopping and rejecting when a string is not in the language). JFLAP 7 seems to use a somewhat different count for the number of nodes generated, and the number for that doesn't always appear to be logically consistent since the parser tracks considered, being-considered, and deleted nodes, which made it harder to directly compare but did help us realize that was something that was problematic and needed to be redone.
Afterwards, Julian talked to us about how he would like to redesign the saving mechanism in JFLAP, in which the information for the current automaton, grammar, or other object is written to an XML file that can be loaded back later. There will essentially be a significantly revamping of how JFLAP saves to XML, and he showed us an example file of his vision for how the new XML format will look. This sounds like an incredibly interesting project, but although Ian and I both have moderate knowledge/experience with XML from taking 108, we thought it would be best to defer this project to Julian at least for its initial stages so that he could implement his desired framework more efficiently since he's also more proficient with XML. Instead, I will be working with Ian in the upcoming weeks to incorporate languages and set theory into JFLAP, and we started brainstorming ideas for different classes and interactive features on the board, then beginning to translate them into Eclipse. Julian gave us some ideas he had for languages/sets, and it sounds like this will be a large but interesting and challenging project to work on! I've started working on a simple class with Ian that will take a given grammar and automatically generate different strings that it can derive.
previous day | next day | return to calendar
More work ensued with the new languages/sets package today. I worked on adding language set operators today (in addition to basic set operations like union, intersection, powerset, etc.), including the Kleene Star, which was surprisingly a bit trickier than I had anticipated. Later in the afternoon, I started thinking about Venn Diagrams, which are the most popular way to visualize sets, and did some online reading about drawing shapes (mainly circles) in Swing; the actual shape rendering seems fairly straightforward, but figuring out the areas of intersection and being able to map that conceptually, such as with labels of the elements in the intersection, will be much trickier. This is probably thinking ahead a bit, but I'm not quite sure where exactly the code is going just yet and I figured having a better sense of what challenges to expect down the road would be useful knowledge to gain. In addition to sets, earlier in the day Ian and I also worked on converting various automata (finite state acceptors and pushdown automata) into fairly reduced grammars; the motivation here was that we were able to generate strings for fairly small grammars, but the grammar that were converted from automata tended to be very large and have useless or lambda productions that were greatly increasing the run time and making it impossible to generate more than one string before hitting an out of memory exception.