grammar for bytecodes ?

ajr@reider.net (Alan Reider)
30 Jun 1997 22:49:16 -0400

          From comp.compilers

Related articles
grammar for bytecodes ? ajr@reider.net (1997-06-30)
| List of all articles for this month |

From: ajr@reider.net (Alan Reider)
Newsgroups: comp.compilers,comp.lang.smalltalk
Date: 30 Jun 1997 22:49:16 -0400
Organization: Spacelab.net Internet Access
Keywords: code, parse, question

I'm wondering if its possible to come up with a grammar for a stack
based VM instruction stream such as Smalltalk which would enable
top-down (recursive descent) parsing.


As an example, consider the following grammar loosely based on
Smalltalk:


MessageExpression :=
        unaryExpression
        | keywordExpression
UnaryExpression := primary [unarySelector]* "0 or more"
KeywordExpression := unaryExpression [keyword unaryExpression]+
"1 or more"
Primary := varName
        | literal
        | '(' MessageExpression ')'


The statement:


        aView addView: (aTopPane addSubPane: (aButton text: 'ok'
asUppercase))


might be compiled to:
        push 'ok'
        send asUppercase
        push aButton
        send #text:
        push aTopPane
        send #addSubpane
        push aView
        send: #addView:


The question is, is there a grammar that can represent this bytecode
'language'? For example:


MessageExpression :=
        unaryExpression
        | keywordExpression
UnaryExpression := push primary [send selector]*
KeywordExpression :=
        unaryExpression [unaryExpression*] send selector




doesnt work because it would only recognize the byteCodes
corresponding
to (aButton text: 'ok' asUppercase) instead of the outermost
expression.


I suspect there is no grammar but i'm not up enough on compiler theory
to explain why (something about tail recursion or LL something or
other:)


I know that bytecodes can be parsed (decompiled) by 'executing' them
using a stack (eg pushing message nodes instead of evaluating message
sends). At the end the stack contains the parse tree.


But I'm curious if it can be done with recursive descent.
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.