regular expressions

schmitta · 10-14-2013, 11:29 AM

If STRUCT ENTRY was an array of structures then the array could be sent to the target as is and storage could be malloc allocated on the target. The array would still be valid as the indexes are virtual. I guess int on the pc is 32 bits but the int index on the target would be 16 bit. But the indexes would still be valid as long as the struct size was known on the target. If code generation were done I would probably like to go for the java like abstract machine on the target but a simple one of course. Then the language could be ported to other machines maybe even as open source although I would need some proprietary code to access the target mcu's peripherals. What do you think and thank you for your input.

jpollard · 10-14-2013, 11:41 AM

That is the advantage for the JVM approach. It even works for the threaded code as the runtime portion of threaded code is just a library of functions. The only difference between them and a subroutine is that the starting address value serves as the threaded code "instruction", and instead of a return, the last instruction(s) are those needed to update the thread version of a PC, and an indirect jump.

Neither require application code (which uses the library) to be of the same license. For the threaded code it is "linked" to the runtime, and the runtime can have anything in it desired, thus a separate license, and only combined by user when the target object code is generated.

The advantage of adding the jump table is that instead of using the addresses directly, the thread instruction is used as an index into the jump table - thus needing a few more instructions, but making the application completely independent of the runtime, and not requiring a "link them together" step other than the vm needing a loader to put it in an appropriate place in memory.

In either case, it is not possible (usually due to the lack of memory protection) to separate the virtual machine entire from the application - but it is very very close, as the vm just copies the "application" into a typeless (or nearly so) array before starting interpretation. If the two can be combined externally (installed into the flash as a unit), you eliminate the need for the VM load - and only the base boot loader would be used to copy from flash to ram. In some architectures, the "ram" would also be the flash - and eliminate the entire loader. It would all look like the bios at that point.

jpollard · 10-14-2013, 12:19 PM

Quote:

Originally Posted by schmitta

If STRUCT ENTRY was an array of structures then the array could be sent to the target as is and storage could be malloc allocated on the target. The array would still be valid as the indexes are virtual. I guess int on the pc is 32 bits but the int index on the target would be 16 bit. But the indexes would still be valid as long as the struct size was known on the target. If code generation were done I would probably like to go for the java like abstract machine on the target but a simple one of course. Then the language could be ported to other machines maybe even as open source although I would need some proprietary code to access the target mcu's peripherals. What do you think and thank you for your input.

Sorry, forgot to answer the first part of your question about struct entry.

The problem with that is the size of the struct entry - there is no need to bulk up most of the structures - If you look, almost none of them are fully used - most only use the left/right pointers.

Converting the tree into a code sequence eliminates the structure entire, and saves all the memory and time needed to walk the tree during execution. Effectively the walking is done during the final translation, thus the VM/interpreter doesn't have to do that work.

schmitta · 10-14-2013, 04:05 PM

I have the .lex code of:

Code:

%{
#include "test.tab.h"
#include <stdlib.h>
%union
{
    int   intValue;
    char  charValue;
    char  *stringValue;
}
%}
%option yylineno
WHITE  [ \t]+
DIGIT [0-9]
BINARY 0[bB][01]+		{yylval.stringValue = strdup(yytext); return BINARY;}
HEX 0[xX][0-9A-Fa-f]+		{(void) sscanf(yytext,"%x",&yylval.intValue); return HEX;}
DEC -{0,1}[0-9]+		{yylval.intValue = atoi(yytext); return DEC;	}
CHARACTER {SQ}[^"\0"]{SQ}	{yylval.stringValue = strdup(yytext);       return CHARACTER;}
CHARS [^"\0"]+			{yylval.charValue = yytext;       return CHARS;}

with the following bnf and parser coding:

Code:

constant:	HEX		{$$=$1<intValue>.value;}
	| 	DEC		{$$=$1<intValue>.value;}
	|	CHARACTER	{$$=$1<charValue>.value;}
	|	BINARY		{$$=$1<stringValue>.value;}
	|	string		{	}
	;

string	:	DQ CHARS DQ	{$$=$2<stringValue>.value;}
	;

is this the correct interpretation of what you want to do?

jpollard · 10-15-2013, 05:14 AM

Semantically, there is no difference between HEX, or DEC. If you notice (the result of both is an int), the scanner specification turns them into an integer, so that the syntax element constant only needs "NUMBER" for these two.

I think there is a scanner problem though.

How is the scanner going to handle a input sequence like "v=a-5" (an expression), from "v= -5" (a constant)?

If the "-5" is handled as a CONSTANT, then the expression is syntactically wrong. The problem is cause by the "-" to set the negative. The parsing of the expression (whether "a-5" or "-5") would be identified differently, the "expression - CONSTANT", or "- CONSTANT" separately. An optimizing pass would identify the difference between the the first and second case, and then collapse the "- CONSTANT" into a single element where the constant is a negative. It could be done during a parse, but it requires the action routine for the parse to look at the "- expression" subtree to decide if it is a constant and can be collapsed into a negative constant.

Now semantic handling of the constants can be done in different ways...

My original thought (not necessarly valid, mind), was to store the various constants in different tables, one table for each type (it does mean a different search function for each table, or a parameter to tell a search function which type to look for). The tables provide a way to accomplish duplicate elimination (saving memory, and better data packing in the target system). It also reduces the number of types for the parse tree to just pointers to entries in the various tables. If the table structure definition can contain all types, then the parse tree only needs to contain references to either the parse tree (forming the tree), or pointer to a table entry. It does mean that the scanner would be the one to enter the constants into the various tables and not done in the action portion of the parser rules (which would provide updates to the table in form of attribute flags and such).

One of the purposes of the tables (outside the duplication elimination) is to carry extra information (the attributes, and the "other" field) which can be used when generating code, and possible debugging information (semantic errors - like making the value of a character too large, conversion of an integer to a character, character to an integer...).

schmitta · 10-15-2013, 06:30 AM

Note that in my larger grammar I have an expression broken down to unary minus as in the following:

Code:

%{
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "apsbasic.h"
extern int yylex();
extern char* yytext;
extern int yylineno;

%}
/*%glr-parser */

%token INT PLUS MINUS MULT DIVIDE MOD POWER LP RP LB RB
%token NOT OR AND XOR ANDAND OROR ENDIF
%token ANDEQ BINARY CHAR CHARACTER COLON COMMA 
%token DIVIDEEQ DQ EOL EQ EQEQ GE GT HEX LABEL LT LE 
%token MINUSEQ MINUSMINUS MODEQ MULTEQ NE OREQ PLUSPLUS
%token PLUSEQ PRINT SEMI SL SLEQ SR SREQ ID
%token WEND XOREQ CHARS DEC PSTART PEND REPEAT
%token INPUT GOTO GOSUB EXIT IF RETURN THEN ELSE WHILE 
%token NEXT END DO UNTIL FOR TO STEP COMMENT EOFF DCL
%token LINE IFELSE
%left PLUS MINUS MULT DIVIDE MOD 
%right POWER
%start pgm
%%
pgm	:			/* empty */
	|	begend lines begend EOFF	{$$=pgm($2);		}
	;

begend	:	PSTART				{$$=pstart();		}
	|	PEND				{$$=pend();		}
	;

lines	:	line				{$$=lines_gen(null,$1);	}
	|	lines line			{$$=lines_gen($1,$2);	}
	|	lines error
	;

line	:	LABEL COLON dcl_stmt eol	{$$=line_gen($1<stringValue>.value,$2);}
	|	dcl_stmt eol			{$$=line_gen(null,$1);	}
	|	LABEL COLON eol			{$$=line_gen($1<stringValue>.value,0);}
	;

eol	:	'\r'
	|	'\n'
	|	"\r\n"
	;
 
dcl_stmt:	statements						{$$=statements_gen($1,null);}
	|	DCL INT ID						{$$=dcl_int__gen($3.value);}
	|	DCL INT ID LB exp RB					{$$=dcl_array_int__gen($3.value,$5,null,null,null);}
	|	DCL INT ID LB exp COMMA exp RB				{$$=dcl_array_int__gen($3.value,$5,$7,null,null);}
	|	DCL INT ID LB exp COMMA exp COMMA exp RB		{$$=dcl_array_int__gen($3.value,$5,$7,$9,null);}
	|	DCL INT ID LB exp COMMA exp COMMA exp COMMA exp RB	{$$=dcl_array_int__gen($3.value,$5,$7,$9,$11);}
	|	DCL CHAR ID						{$$=dcl_char__gen($3.value);}
	|	DCL CHAR ID LB exp RB					{$$=dcl_array_char__gen($3.value,$5,null,null,null);}
	|	DCL CHAR ID LB exp COMMA exp RB				{$$=dcl_array_char__gen($3.value,$5,$7,null,null);}
	|	DCL CHAR ID LB exp COMMA exp COMMA exp RB		{$$=dcl_array_char__gen($3.value,$5,$7,$9,null);}	
	|	DCL CHAR ID LB exp COMMA exp COMMA exp COMMA exp RB	{$$=dcl_array_char__gen($3.value,$5,$7,$9,$11);}
	;

statements:	statement					{$$=statement_gen($1,null);}
	|   	statements statement				{$$=statement_gen($1,$2);	}
	;

statement:	var EQ exp					{$$=eq_gen($1,$3);	}
	|	GOTO LABEL					{$$=goto_gen($2.value);	}
	|	GOSUB LABEL					{$$=gosub_gen($2.value);	}
	|	IF exp THEN statements ENDIF			{$$=if_gen($2,$4);	}
	|	IF exp THEN statements ELSE statements ENDIF	{$$=ifelse_gen($2,$4,$6);	}
	|	RETURN						{$$=return();		}
	|	END						{$$=end_gen();		}	
	|	WHILE exp statements WEND			{$$=while_gen($2,$3);	}
	|	REPEAT statements UNTIL exp			{$$=repeat_gen($2,$4);	}
	;
	
var	:	ID						{$$=$1;				}
	|	ID LB exp RB					{$$=array_gen($3,null,null,null);	}
	|	ID LB exp COMMA exp RB				{$$=array_gen($3,$5,null,null);	}
	|	ID LB exp COMMA exp COMMA exp RB		{$$=array_gen($3,$5,$7,null);	}
	|	ID LB exp COMMA exp COMMA exp COMMA exp RB	{$$=array_gen($3,$5,$7,$9);	}
	;
	
exp	:	add_exp				{$$=exp_gen($1);		}
	|	exp EQEQ add_exp		{$$=eqeq_gen($1,$3);	}
	|	exp NE   add_exp		{$$=ne_gen($1,$3);	}
	;

add_exp	:	mult_exp
	|	add_exp PLUS mult_exp		{$$=plus_gen($1,$3);	}
	|	add_exp	MINUS mult_exp		{$$=minus_gen($1,$3);	}
	;

mult_exp:	prim_exp
	|	mult_exp MULT prim_exp		{$$=mult_gen($1,$3);	}
	|	mult_exp DIVIDE prim_exp	{$$=divide_gen($1,$3);	}
	|	mult_exp MOD prim_exp		{$$=mod_gen($1,$3);	}
	;

prim_exp:	var				{$$=var_gen($1);		}
	|	constant			{$$=const_gen($1);	}
	|	LP exp RP			{$$=exp_gen($2);		}
	;

constant:	HEX				{$$=$1<intValue>.value;}
	| 	DEC				{$$=$1<intValue>.value;}
	|	CHARACTER			{$$=$1<charValue>.value;}
	|	BINARY				{$$=$1<stringValue>.value;}
	|	string				{		}
	;

string	:	DQ CHARS DQ			{$$=$2<stringValue>.value;}
	;
%%
int yyerror (char *s)
{
	printf("%s on line %d - %s\n",s,yylineno,yytext);
}
int main ()
{
	if (yyparse())
		fprintf(stderr,"Successful Parsing.\n");
	else 
		fprintf(stderr,"error found.\n");
}
int get_struct_entry();
{
	entry_index = entry_index + 1;
	if (entry_index>=RAMLIMIT) {
		fprintf(out,"\r\nLimit exceeded on struct entry ( %d )\r\n",RAMLIMIT);
		exit(1);
		}
	return entry_index;
}
int get_struct_symbol();
{
	symbol_index = symbol_index + 1;
	if (symbol_index>=SYMBOLLIMIT) {
		fprintf(out,"\r\nLimit exceeded on struct symbol ( %d )\r\n",SYMBOLLIMIT);
		exit(2);
		}
	return symbol_index;
}
int while_gen(
		int exp,	// expression
		int statements)	// statements
{
	int i=get_struct_entry();
	struct_entry[i]->entry_type 	= WHILE;
	struct_entry[i]->left 		= exp;
	struct_entry[i]->center 	= 0;
	struct_entry[i]->right 		= statements;
	struct_entry[i]->symbol 	= 0;
	return (i);
	
}
int if_gen(
		int	exp,	// expression
		int	stmt)	// statements
{
	int i = get_struct_entry();
	struct_entry[i]->entry_type	= IFONLY;
	struct_entry[i]->left		= exp;
	struct_entry[i]->center		= 0;
	struct_entry[i]->right		= stmt;
	struct_entry[i]->symbol		=0;
	return (i);
}
int ifelse_gen(
		int	exp,		// expression
		int	ifstmt,		// if part statements
		int	elsestmt)	// else part statements
{
	int i = get_struct_entry();
	struct_entry[i]->entry_type	= IFONLY;
	struct_entry[i]->left		= exp;
	struct_entry[i]->center		= ifstmt;
	struct_entry[i]->right		= elsestmt;
	struct_entry[i]->symbol		=0;
	return (i);
}
unsigned int find_symbol (char *name)
{
	for (int i = 1; i<symbol_index;i++) 
		if (name==struct_symbol[i]->symb) return i;
	return 0;		
}
struct st_return put_symbol (
				char * name,	    // pointer to symbol name
				unsigned char type, // see: ST_ #defines.
				unsigned char flags,// see: defined flags section
				unsigned int  line, // Line number where found.
				unsigned int  dim1, // first dimension
				unsigned int  dim2, // second dimension
				unsigned int  dim3, // third dimension
				unsigned int  dim4) // forth dimension
{
	if(!(int k=find_symbol(name))){
		int j = get_struct_symbol();

		struct_symbol[j]->symb  	= label;
		struct_symbol[j]->sym_type	= ST_LABDEF;
		struct_symbol[j]->flags		= NONE;
		struct_symbol[j]->line		= yylineno;
		for (int k=0; k<NUMDIM; k++) struct_symbol[j]->dimsize[k]=0;
		st_return->isitin=0;
		st_return->linenum=yylineno;
		st_return->location=j;
		return st_return;
		}
	else {
		st_return->isitin=-1;
		st_return->linenum=struct_symbol[k]->line;
		st_return->location=k;
		return st_return;
		}
}
int line_gen(
		char 	*label,		// pointer to label string.
		int	statements)	// index to statments 
{
	int i = get_struct_entry();
	struct_entry[i]->entry_type		= LINE;

	if (label==null)
		struct_entry[i]->symbol		= 0;
	else {
	st_return k = put_symbol (label,ST_LABDEF,NONE,yylineno,0,0,0,0);
	if (k->isitin==-1) fprintf(out,
			"Symbol already defined at line number: %d Symbol table loc: %d\r\n",st_return->linenum,st_return->location);
		struct_entry[i]->symbol 	= k->location;
		struct_symbol[j]->other		= 0;
		}
		struct_entry[i]->center		=0;
		struct_entry[i]-right		=0;
	if (statements==0) 
		struct_entry->left		= 0;
	else
		struct_entry->left		=statements;
	return (i);		
}
/*
int const_gen(
		int type,		// Parser constant  
		char *strvalue)		// for bin char and str
{
	int i = get_struct_entry();
	struct_entry->entry_type		= type;	
	struct_entry[i]->entry_type	= type;
	struct_entry[i]->left		= 0;
	struct_entry[i]->center		= 0;
	struct_entry[i]->right		= 0;
	if (decvalue!=0) {
		st_return k = put_symbol (
	struct_entry[i]->symbol		= ;
	return (i);
}
*/
}

with .lex as the following:

Code:

%{
#include "test.tab.h"
#include <stdlib.h>
%union
{
    int   intValue;
    char  charValue;
    char  *stringValue;
}
%}
%option yylineno
WHITE  [ \t]+
DIGIT [0-9]
BINARY 0[bB][01]+		{yylval.stringValue = strdup(yytext); return BINARY;}
HEX 0[xX][0-9A-Fa-f]+		{(void) sscanf(yytext,"%x",&yylval.intValue); return HEX;}
DEC -{0,1}[0-9]+		{yylval.intValue = atoi(yytext); return DEC;	}
CHARACTER {SQ}[^"\0"]{SQ}	{yylval.stringValue = strdup(yytext);       return CHARACTER;}
CHARS [^"\0"]+			{yylval.charValue = yytext;       return CHARS;}		
MULTEQ "*="
DIVIDEEQ "/="
MODEQ "%="
PLUSEQ "+="
MINUSEQ "-="
SLEQ "<<="
SREQ ">>="
ANDEQ "&="
OREQ "|="
XOREQ "^="
POWEREQ "**="
NOT '!'
OR '|'
AND '&'
XOR '^'
OROR "||"
ANDAND "&&"
PLUSPLUS "++"
MINUSMINUS "--"
SL "<<"
SR ">>"
EQ '='
EQEQ "=="
NE "!="
GE ">="
LE "<="
GT '>'
LT '<'
COMMA ','
COLON ':'
SEMI ';'
LB '['
RB ']'
LP '('
RP ')'
DQ "\""
SQ "\'"
ID [A-Za-z_][A-Za-z0-9_]*
LABEL ^{ID}			{yylval.stringValue = strdup(yytext); return LABEL;}
COMMENT "//".*
%%
{WHITE}		{		}
"line"		{return LINE;	}
"int" 		{return INT;	}
"char"		{return CHAR;	}
"*="		{return MULTEQ;	}
"/="		{return DIVIDEEQ;}
"%="		{return MODEQ;	}
"+="		{return PLUSEQ;	}
"-="		{return MINUSEQ;}
"<<="		{return SLEQ;	}
">>="		{return SREQ;	}
"&="		{return ANDEQ;	}
"^="		{return XOREQ;	}
"|="		{return OREQ;	}
'!'		{return NOT;	}
'|'		{return OR;	}
'&'		{return AND;	}
'^'		{return XOR;	}
"||"		{return OROR;	}
"&&"		{return ANDAND;	}
"<<"		{return SL;	}
">>"		{return SR;	}
'+'		{return PLUS;	}
'-'		{return MINUS;	}
"++"		{return PLUSPLUS;}
"--"		(return MINUSMINUS;}
'*'		{return MULT;	}
'/'		{return DIVIDE;	}
'%'		{return MOD;	}
"**"		{return POWER;	}
'('		{return LP;	}
')'		{return RP;	}
'['		{return LB;	}
']'		{return RB;	}
"input"		{return INPUT;	}
"goto"		{return GOTO;	}
"gosub"		{return GOSUB;	}
"exit"		{return EXIT;	}
"if"		{return IF;	}
"ifelse"	{return IFELSE;	}
"return"	{return RETURN;	}
"then"		{return THEN;	}
"else"		{return ELSE;	}
"while"		{return WHILE;	}
"next"		{return NEXT;	}
"end"		{return END;	}
"repeat"	{return REPEAT;	}
"do"		{return DO;	}
"until"		{return UNTIL;	}
"for"		{return FOR;	}
"to"		{return TO;	}
"step"		{return STEP;	}
"dcl"		{return DCL;	}

How should I change the code to satisfy your complaint? Thanks. Alvin...

schmitta · 10-15-2013, 09:00 AM

I still do not understand why the STRUC ENTRY and STRUC SYMBOL arrays cannot be passed as is to the mcu and the entry tree walked by the interpreter. Then no labels would be needed.

jpollard · 10-15-2013, 02:33 PM

Quote:

Originally Posted by schmitta

I still do not understand why the STRUC ENTRY and STRUC SYMBOL arrays cannot be passed as is to the mcu and the entry tree walked by the interpreter. Then no labels would be needed.

I didn't mean "cannot". It just adds more processing overhead, and memory overhead - a minimum of about 8 bytes per structure, and the added indexing to perform the equivalent of a simple jump. It also adds to simple a + b, as there are three entries - one for a, one for b, and one for the plus (which would be 24 bytes). And depending on the arch, direct code format only needs two load instructions and an add, usually coming out to about 7 bytes. Using a basic threaded code form (push a, push b, add) only uses 10 bytes (assuming everything is in a two byte length).

Conversion from the tree into a more appropriate target form eliminates the tree walking overhead from the target (it is still done, but on the translating PC, not the embedded system).

The parsing operation would first analyze something like "A = B + C", turning it into the parse tree:

Code:

     a   =  b + c

            |
    assign--+---------+
            |         |
            |         |
            a         |
                add---+----+
                      |    |
                      |    |
                      b    c

If each level of the tree needed 6 bytes, then the tree has 12 bytes and the symbol table entries for a,b,and c(even if it only needed 4 bytes each - something for the type of each a,b,c and storage for the value for a,b,c is 12 more bytes, for a total of 24.

A translation of that into a basic stack machine would make it:

Code:

push  b   (push value)
push  c   (push value)
add       (pop b,c add, then push result)
pop   a   (pop value of a+b, address of a, store value in a)

If a simple threaded code implementation (2 bytes for each active element) this adds up to 14.

It also allows the elimination of having to track the data types - that tracking is done during the translation phase to select the correct operators. For instance, if a/b/c were 32 bits instead of 16, perhaps the interpreter defines a "push", "push2", "push4" operations - in which case, for a 32bit sequence
it becomes:

Code:

push4 b
push4 c
add4
pop4  a

And still only needs 14 bytes, but no runtime checking for data types (that was done during code generation). Dynamic types can also be handled, but then there would only be one operating function instead of 3 - and they would look at the data types associated with the variable (same as with the symbol table) to determine how many bytes to push, add, and store. But the basic code size remains 14.

Granted, I am assuming there is an assembler available for the target machine (there usually is one).

jpollard · 10-15-2013, 02:38 PM

Are you allowed to tell me which CPU is being used? (I don't want the entire system, just the cpu core instructions, and CPU limitations would be useful).

jpollard · 10-15-2013, 04:18 PM

Quote:

Originally Posted by schmitta

Note that in my larger grammar I have an expression broken down to unary minus as in the following:

Code:

...
exp	:	add_exp				{$$=exp_gen($1);		}
	|	exp EQEQ add_exp		{$$=eqeq_gen($1,$3);	}
	|	exp NE   add_exp		{$$=ne_gen($1,$3);	}
	;

add_exp	:	mult_exp
	|	add_exp PLUS mult_exp		{$$=plus_gen($1,$3);	}
	|	add_exp	MINUS mult_exp		{$$=minus_gen($1,$3);	}
	;

mult_exp:	prim_exp
	|	mult_exp MULT prim_exp		{$$=mult_gen($1,$3);	}
	|	mult_exp DIVIDE prim_exp	{$$=divide_gen($1,$3);	}
	|	mult_exp MOD prim_exp		{$$=mod_gen($1,$3);	}
	;

prim_exp:	var				{$$=var_gen($1);		}
	|	constant			{$$=const_gen($1);	}
	|	LP exp RP			{$$=exp_gen($2);		}
	;
...

How should I change the code to satisfy your complaint? Thanks. Alvin...

There is no unary minus there. The grammar you have only allows for value-value... I believe this grammer (plus the - handling in the scanner) would allow for a "(var + -5)", which looks strange. It would NOT allow for "(var-5)" as the -5 is consumed by the scanner.

I think the following should work:

Code:

prim_exp:	var				{$$=var_gen($1);		}
	|	constant			{$$=const_gen($1);	}
        |       unary_ops
        ;

unary_ops:      MINUS var
        |       MINUS constant
        |       MINUS unary_ops
	|	LP exp RP			{$$=exp_gen($2);		}
	;

As that will allow a "-var", "-5", and "-(expression)". At least it has no shift/reduce conflicts in the grammar I'm using for an example. I'm not sure what your production rules for those added pieces would be though. The one for unary_ops in prim_exp should be the default as the tree built should be what is returned from unary_ops rather than a newly generated entry.

schmitta · 10-15-2013, 07:25 PM

I will add the unary minus to the grammar. I agree and think I will use a 32 bit wide stack that will handle signed int32, string pointers and floating point which is also 32 bit. I may also need a costack next to it to hold unsigned char number indicating what type the associated value is on the stack. My whole idea is to use the CCS C compiler as it has built in functions for the peripherals I plan to allow the user to access with the language. I can't supply the compiler with the product so I was going to have an interpreted assembler and a pseudo assembler code to run in the target which would activate associated CCS C functions to execute the code. The device is a microchip PIC24EP512GP806 16 bit machine with 170k words of flash and 53k of ram. The machine has a 16 deep hardware stack for return addresses. I will also use a packet between the pc and the pic24 (over the usb) so I can provide a code update to the mcu over the USB using a bootloader.

I am not the swiftest person in all this so I am having trouble knowing which bnf lines to assign entry structures to and which to just do say $$=$2 to. Also it has been years since I wrote a tree walking routine so I may need help designing that. Maybe the struc entry needs a bit for marking that that part of the tree has already been traversed. Thank you for your help. Alvin....

jpollard · 10-15-2013, 08:42 PM

Willing to try. I admit to not being familar with the PIC 24, but I think some things can help with the interpreter - the limited stack isn't a problem for a threaded code interpreter (even when using an index table) as the interpreter itself may use the hardware stack, but the threaded code itself doesn't. That can use a software implemented stack which wouldn't have the same limitations. Implementing the interpreter in C for the pic makes it easer to use the index table. The virtual machine/threaded code data stack might be 16 bit aligned, with two stack entries providing a 32 bit unit. That would reduce the amount of lost space.

Hopefully I'll have an example set (I've been delayed a bit). I have a grammar, and most of the scanner, and am working on the table support (using 4, one for characters, one for numbers, one for strings and one for program symbols). So I've started testing those. A tree walker to translate to a pcode/threaded code style interpreter is not complicated. No need to even mark entries that have been processed. Since it runs on the PC time isn't an issue - but the output code would end up on the target system (or an emulator for interpreter).

schmitta · 10-16-2013, 10:38 AM

Maybe I am backwards. Maybe I should be developing the pseudo assembly stack abstract language for the target first. Should I have three stacks? One for 32 bit INTs and FLOATs, One (16 bit) for STRING pointers and one for (8 bit) CHARs? Should I pass declare statements through as is?

Code:

 
DCL INT abc,def=-3249576
DCL CHAR achar='A'
DCL STRING a="This is a test"

and would I need flex and bison to decode the DCL statements? What operations would I need?

jpollard · 10-16-2013, 01:10 PM

1) Not necessarily backwards. The goal is the application, and that takes looking at the beginning (the language of the application), and the target (where it will run). Then something in between to provide the translation. So far, I think you have focused on the application, and the beginning of the "in between". So now the target gets looked at.

2)
No - that way would result in lost space.

3) And yes, flex and bison would parse the declarations, and generate appropriate symbol table entries, that can be referenced during a code generation.

An abstract stack machine is very simple (easy to generate code for as well), but such a "machine" interpreter only requires two varibles (as far as the code being interpreted)...

a generic stack (it is up to the code to track whether an entry is 1, 2, 4, 8 bytes long), a program counter (index into the code array), and a working memory (for variables...). In hardware, all three share the same memory, but the advantage for an interpreter is that it can emulate a read-only program store...

Most such programs have three parts:

Code:

+-------------------------+
| application             |
| code (read only)        |
|                         |   This part may be a separate array...
|                         |
+-------------------------+
| general storage         |
|(ints, strings,          |
| bytes, floats           |
| both constants and      |   This part could be a separate array... but can make things confusing
| variable, though        |   for debugging (indexes to data depend on where the base is...)
| strings would have      |   For instance, what is the difference between an index into a constant table
| a fixed maximum         |   vs an index to a datum on the stack? If the constant table is in the code
| size)                   |   then it gets tricky.
|                         |
+-------------------------+
| heap storage            |
| dynamically allocated   |
| (might not exist)       |     Might not exist, but is usually whatever the stack doesn't use.
| grows |                 |
|       V                 |
+-------------------------+
| (stack space)           |
...                     ...
|                         |
|       /|\               |     Is usually part of the same memory as the heap
| grows toward top        |     which allows them to share space
|(bottom of the stack)    |
+-------------------------+

I have even seen some divide it up differently, putting the stack first, then the program code, static variables (in the C sense) and constants, followed by the heap. (RT-11 for the PDP-11 did that - a pain to change the stack size).

This is also roughly the usual memory image of most applications. If you think of the interpreter as a machine, the rest tends to fall out. Indexing everything the same way makes it simpler, and without special cases. One issue that crops up is more dependant on the hardware being used - if memory accesses have an alignment requirement (such as 16/32 bit ints and floats must be on an even address...) it makes the interpreter have to stick to those alignment restrictions, or add some overhead to first move the data to an appropriately aligned area before operating on it (such as having to move 4 byte data somewhere to make them available for the hardware floating point operation, and then move the result back to the non-aligned interpreter view of the storage.

Now for "DCL CHAR achar='A'" (the simple case)
The parsing table would have a tree defining what this represents.. (and there can be two variations too).

The 'A' can be identified as a character (a ' can be used as C uses it to identify single characters),
So the assignment to achar would occur, either as a character, or as an int (either could be valid). The DCL CHAR would give the variable achar the attribute of being a character. Using just the assignment could make the variable (without even a DCL CHAR) to be a character. Now translation COULD be done in two ways - tread achar as a variable receiving a value:

Code:

pushci 'A'    (push character immediate, followed by the ascii value A)
popc   achar  (where achar is assigned to be a byte...)
...
achar:  byte  (assign a byte storage for the variable achar)

OR...

Code:

achar: 'A'    (same as the c declaration char achar = 'A'; which may be a variable OR const)

The first requires runtime execution to get the value set, it can be thought of as the same as a declaration in C used within a function: "void xyz(char c) { char achar = c;...". The second just has it as the initial value for achar. The second depends on the translator to interpret the "variable = expression" part of the parse tree such that it can do this form IF the expression is a constant (or derived from other constants...). It must do the first if the expression has any kind of variable in it.

schmitta · 10-17-2013, 12:56 AM

Can flex return the byte address in the buffer of the token it has found ? What variable would it be returned in?