RSS Feed

Peter Goodman's blog about PHP, Parsing Theory, C++, Functional Programming, Applications,

As part of Granary, I have developed a sort-of GNU C99 type and function declaration parser, which is now hosted on GitHub. I am releasing this code because others might find it useful. There are a number of other implementations out there; however, when I last tried them, none met my exact needs (parsing glibc headers, Darwin libc headers, and Linux kernel headers).

This parser is not particularly novel, and likely contains bugs (I am 100% sure that the file has bugs). However, it has also been very useful.

I welcome feedback, bug fixes, feature requests, or feature additions to this parser from interested third parties.

Recently I presented a poster at OSDI'12. The poster outlined our use of dynamic binary translation (DBT) for analysing operating system (OS) kernel modules. One novelty of our approach is that we ensure that only module code is analysed; non-module kernel code is never translated. This restriction entails taking control when module code executes (so that it can be translated) and relinquishing control when non-module kernel code executes. To regain control when kernel code invokes module code, we proactively search for and change function pointers in shared data structures.

Proactively changing function pointers that potentially point into module code is achieved by interposing on the interface between modules and the kernel. Modules and the kernel share data structures, and those data structures can contain function pointers. Finding and changing function pointers requires recursively applying a replacement function to the fields of data structures, starting from the "root" function arguments. Without guards in place, this recursive process might not terminate (e.g. a cyclic data structure). In the case of deeply linked data structures (e.g. trees), this recursive process might be expensive. To avoid this expense, we apply the replacement function only to those data structures that have changed.

Read the rest of this article »

One parsing technique that I sometimes use is Top Down Operator Precedence Parsing (TDOP). TDOP parsers have been discussed in many other places as well. Unfortunately, I have not seen TDOP described in terms of left-corner parsing (except for a passing comment in this thesis).

The purpose of this post is to set the stage for a later discussion about TDOP parsing. This post will introduce top-down and bottom-up parsing, then combine the two methods to introduce left-corner parsing. Also, the top-down parsing language (TDPL) will be briefly mentioned as its semantics relate to TDOP.

Read the rest of this article »

Recently I worked on a project for my Optimizing Compilers course. The purpose of this project was to implement Loop-invariant Code Motion and any other compiler optimizations that we choose. The project is competitive because one's mark is based on how one's compiler improves the mean execution time on a small set of static, pre-determined test cases. Given that the test cases do not change, it is natural to specialize one's optimizations to the code being tested. Realistically, this might not be the best approach as code tends to change and compiler optimizations are not always transparent.

Read the rest of this article »