On Mar 12, 2010, at 9:00 AM, steven Hooley wrote:
>> Bloomin' magic! Thanks, Filip, it worketh well. Hardy souls all.
>> Tom W.
>
> Is it possible to see an example of how this might be used? I'd like
> to understand Bison/Yacc better and i think an example relevant to
> Cocoa / Objective-C would really help.
>
> Thanks,
> Steven
Steve,
The interpreter I am working on is a work in progress, but here is a copy of
the yacc/bison file as it exists as I start work on it today. It imports (not
includes) the Cocoa Foundation and the semantic actions are written in
Objective-C. This file is incomplete as it is only two days old and I am in the
process of writing the semantic actions for the statement and expression types
now. But you can still see the statement and expression types that will be
handled by reading the grammar. The language itself is nearly complete. As it
stands now it has only one shift/reduce conflict, that caused by the inherent
ambiguity in the if/else statement, but the yacc/bison approach to resolving
these conflicts by using shift is the proper handling in this case. (All this
means is that the parser will make sure that else statements bind to the
closest "then" part.)
This is a typical example of using yacc/bison. The language defined is a
general purpose programming language. During parsing a semantic tree of the
program is built out of Objective-C objects (including the representations of
different kinds of statements and expressions, values, types, modules and so
on). Building the tree is what the semantic actions (the code with the $$ and
$1 things scattered among the rules) do. Once this representation is built, the
tree is validated for programming errors as any normal compiler would do (for
example, undeclared variables, argument/parameter mismatches, assigning a
number to a set, and so on) and then the program is run by an interpreter. The
interpreter is similar to, though much simpler than, the Java virtual machine,
as it executes the semantic trees as if they were instructions to a virtual
machine, while managing the run time stack and the currently active subtree of
symbol tables. I am writing the validator and interpreter in parallel with the
parser, so there is a lot of stuff not visible here.
This is all part of a Cocoa-based genealogical software application, where this
part allows users to run their own algorithms on records in their databases or
to generate their own specialty reports without having to modify the
application itself. The genealogical records (eg, info about events, persons,
families, and so on) are all kept in tree structures that can be represented in
the application's databases or externally as XML or other types of structured
text (GEDCOM is the format often chosen for genealogical software but it
suffers from a variety of limitations.) Thus my earlier and not so positive
reference to XSLT, which is the "official" (and much harder) way to do this,
though I expect that an XSLT "program" would not be able to affect the database
holding the records it processes.
Needless to say I am extremely pleased that all I had to do was make the suffix
to the yacc file be .ym instead of .y to get Xcode to do all the right things.
I don't know whether bison itself was modified or whether the Xcode build rules
just do the proper renaming, but the fact that someone at Apple worried about
it and then made it work, is just one of those little things that makes me so
content, one might even say smirkily self-satisfied, to be developing for the
Mac. And then the fact that someone on this list (thanks, Filip) knew this was
even better, as I have yet to find any actual DOCUMENTATION that states that
this would happen! Easter eggs in spring.
Tom Wetmore, Chief Bottle Washer, DeadEnds Software
// Interpreter.ym
//
// Created by Thomas Wetmore on 3/10/2010.
// Last changed on 3/12/2010.
// Copyright 2010 DeadEnds Software. All rights reserved.
%{
#import <Foundation/Foundation.h>
#import "TWInterpreter.h"
#import "TWInterpStatement.h"
#import "TWInterpExpression.h"
#import "TWInterpModule.h"
#import "TWInterpLexer.h"
// For this parser every semantic type is an Objective-C object.
#define YYSTYPE id
extern TWInterpreterLexer* lexer;
void yyerror (char* message);
int yylex ();
%}
%token TYPE
%right ASGNOP
%left OROP
%left ANDOP
%left EQOP
%left RELOP
%left ADDOP
%left MULOP
%right UNARYOP
%right NOTOP
%token IDEN ICONS FCONS SCONS BCONS
%token WHILE DO IF ELSE
%token BREAK CONTINUE RETURN
%%
definitions : definition
| definitions definition
;
definition : declaration {
[globalDeclarations addObject: $1];
}
| module {
[moduleTable setObject: $1 forKey:
((TWInterpModule*)$1).name];
}
;
declaration : TYPE identifiers m ';' {
$$ = [[[TWInterpDeclaration alloc]
initWithType: $1 variables: $2] autorelease];
((TWInterpStatement*) $$).lineNumber =
$3;
}
;
module : TYPE IDEN '(' parameterso ')' block {
$$ = [[[TWInterpModule alloc]
initWithType: $1 name: $2 parameters: $4 block: $6] autorelease];
}
;
declarationso: declarations {
$$ = $1;
}
| /* empty */ {
$$ = nil;
}
;
declarations: declaration {
$$ = [[[NSMutableArray alloc]
initWithObjects: $1, nil] autorelease];
}
| declarations declaration {
$$ = $1; [$$ addObject: $2];
}
;
identifiers : IDEN {
$$ = [[[NSMutableArray alloc]
initWithObjects: $1, nil] autorelease];
}
| identifiers ',' IDEN {
$$ = $1; [$$ addObject: $3];
}
;
parameterso : parameters {
$$ = $1;
}
| /* empty */ {
$$ = nil;
}
;
parameters : parameter {
$$ = [[[NSMutableArray alloc]
initWithObjects: $1, nil] autorelease];
}
| parameters ',' parameter {
$$ = $1; [$$ addObject: $3];
}
;
parameter : TYPE IDEN
;
statementso : statements {
$$ = $1;
}
| /* empty */ {
$$ = nil;
}
;
statements : statement {
$$ = [[[NSMutableArray alloc]
initWithObjects: $1, nil] autorelease];
}
| statements statement {
$$ = $1; [$$ addObject: $2];
}
;
statement : expression m ';'
| IF m '(' expression ')' statement
| IF m '(' expression ')' statement ELSE statement
| WHILE m '(' expression ')' statement
| DO m statement WHILE '(' expression ')'
| block
| RETURN m expressiono ';'
| CONTINUE m ';'
| BREAK m ';'
;
block : '{' declarationso statementso '}' {
$$ = [[[TWInterpBlockStatement alloc]
initWithDeclaractions: $2 statements: $3] autorelease];
}
;
expression : IDEN
| ICONS
| FCONS
| SCONS
| BCONS
| '(' expression ')'
| IDEN '(' expressionso ')'
| expression ADDOP expression
| expression MULOP expression
| expression RELOP expression
| expression EQOP expression
| expression ANDOP expression
| expression OROP expression
| expression ASGNOP expression
| ADDOP expression %prec UNARYOP
| NOTOP expression
;
expressiono : expression
| /* empty */
;
expressionso: expressions
| /* empty */
;
expressions : expression
| expressions ',' expression
;
m : /* empty */ {
$$ = [[[NSNumber alloc] initWithInt:
lexer.lineNumber] autorelease];
}
%%
_______________________________________________
Cocoa-dev mailing list ([email protected])
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to [email protected]
