Re: Bison/Yacc with Objective-C ?
Re: Bison/Yacc with Objective-C ?
- Subject: Re: Bison/Yacc with Objective-C ?
- From: Thomas Wetmore <email@hidden>
- Date: Fri, 12 Mar 2010 10:18:27 -0500
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@hidden)
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:
This email sent to email@hidden