Monday, January 07, 2008
YEPP, the Eiffel Parser Producer
Bottom-up shift-reduce parsers (such as those generated by Gobo Eiffel Yacc) are flexible and efficient. They run fast because as they scan the input tokens they consider multiple possible constructs at the same time (in parallel, if you like).
Their downside is that it's mighty hard to code them in such a way as to get them to emit really good error messages when they encounter a syntax error. By the time you have added enough error handling to achieve good syntax error messages, you may well have lost the power, convenience and flexibility originally offered by the shift-reduce approach.
An alternative approach is the top-down parser, which in modern programming languages usually makes use of recursive descent to climb down the parse tree. It's likely to be a bit slower than a shift-reduce parser, particularly for grammars that are very complex at the lower levels (expressions downwards).
But if there's a syntax error, the top-down parser can give a very clear and helpful error message based on where it's up to in the descent of the parse tree.
Top-down parsers are fairly straightforward to write, but they are tedious. There's lots of code which follows a fairly repetitive pattern, but with just enough variation from construct to construct that it's hard to abstract out the patterns. If you don't want to write the parser manually, you can use a parser generator (whereas with a shift-reduce parser, you would almost always use a parser generator because of its added complexity).
Cyril Adrian has put together the YEPP Eiffel Parser Producer. It's meant to replace the venerable lex/yacc couple for SmartEiffel users. Its input files use an Eiffelish syntax extended to allow simple grammar declarations in an EBNF notation. Its output is an Eiffel class. It is built using (both in itself and for its output) ESE's parse library, which implements a top-down parsing strategy.
YEPP is part of the Enterprise SmartEiffel project
Top-down parsing is also found in Java's ANTLR parser-generator. Shift-reduce parsing is found in yacc and bison.
Their downside is that it's mighty hard to code them in such a way as to get them to emit really good error messages when they encounter a syntax error. By the time you have added enough error handling to achieve good syntax error messages, you may well have lost the power, convenience and flexibility originally offered by the shift-reduce approach.
An alternative approach is the top-down parser, which in modern programming languages usually makes use of recursive descent to climb down the parse tree. It's likely to be a bit slower than a shift-reduce parser, particularly for grammars that are very complex at the lower levels (expressions downwards).
But if there's a syntax error, the top-down parser can give a very clear and helpful error message based on where it's up to in the descent of the parse tree.
Top-down parsers are fairly straightforward to write, but they are tedious. There's lots of code which follows a fairly repetitive pattern, but with just enough variation from construct to construct that it's hard to abstract out the patterns. If you don't want to write the parser manually, you can use a parser generator (whereas with a shift-reduce parser, you would almost always use a parser generator because of its added complexity).
Cyril Adrian has put together the YEPP Eiffel Parser Producer. It's meant to replace the venerable lex/yacc couple for SmartEiffel users. Its input files use an Eiffelish syntax extended to allow simple grammar declarations in an EBNF notation. Its output is an Eiffel class. It is built using (both in itself and for its output) ESE's parse library, which implements a top-down parsing strategy.
YEPP is part of the Enterprise SmartEiffel project
Top-down parsing is also found in Java's ANTLR parser-generator. Shift-reduce parsing is found in yacc and bison.
posted by Roger Browne @ 22:08 1 comments
Friday, January 04, 2008
Recent version updates
EiffelStudio is now at version 6.1 . Basic elements of the ECMA Eiffel attached type mechanism are supported, as is non-conforming inheritance. ISE describes their non-conforming inheritance as "a first among object-oriented languages", which will surprise many people including those who have been using the corresponding SmartEiffel facility for a year or two, and those who were using the corresponding Sather facility over 15 years ago. Nevertheless it's welcome. (downloads)
By the way, if you are still using the original "agent" syntax of the tilde character, you should change your Eiffel code to use the 'agent' keyword, as your code is going to be broken by a future release of EiffelStudio, where tilde will be used as an operator. ISE offers a tool to help automate this, although if you don't run Windows you're out of luck as it's Windows-only. ISE Eiffel is promoted as being multi-platform, so it would have made more sense to release this as Eiffel source code. At EiffelRoom there's a poll running where you can let the developers know whether you still have code using the old agent syntax.
In November, Eric Bezault released Gobo version 3.7, which supports ISE Eiffel 5.7.64493, 6.0.6.9618 and 6.1.7.1007 (Classic and .NET), SmartEiffel 1.2r7, and Gobo Eiffel Compiler 3.7. The Gobo tools are now bootstrapped by a C program, rather than by Windows and Linux executables as in previous versions.
Also, Berend de Boer has released version 3.0.1 of eposix, his Eiffel to POSIX binding. This is a minor update, to fix a segmentation fault that affected Windows users of STDC_TIME.to_utc. No other users need to update.
By the way, if you are still using the original "agent" syntax of the tilde character, you should change your Eiffel code to use the 'agent' keyword, as your code is going to be broken by a future release of EiffelStudio, where tilde will be used as an operator. ISE offers a tool to help automate this, although if you don't run Windows you're out of luck as it's Windows-only. ISE Eiffel is promoted as being multi-platform, so it would have made more sense to release this as Eiffel source code. At EiffelRoom there's a poll running where you can let the developers know whether you still have code using the old agent syntax.
In November, Eric Bezault released Gobo version 3.7, which supports ISE Eiffel 5.7.64493, 6.0.6.9618 and 6.1.7.1007 (Classic and .NET), SmartEiffel 1.2r7, and Gobo Eiffel Compiler 3.7. The Gobo tools are now bootstrapped by a C program, rather than by Windows and Linux executables as in previous versions.
Also, Berend de Boer has released version 3.0.1 of eposix, his Eiffel to POSIX binding. This is a minor update, to fix a segmentation fault that affected Windows users of STDC_TIME.to_utc. No other users need to update.
posted by Roger Browne @ 14:47 2 comments
