Compilers - Lex and Yacc Newbie Questions!!!

Author

Lex and Yacc Newbie Questions!!!

Hari Sriniv

2004-03-27, 12:29 am

Hello experts,
I have some rudimentary question with the Lex and Yacc. I have been
developing an assembler for the in house processsor. I have assembled
the normal instructions pretty easily using the lex and Yacc. I have
some challenges for the branch instructions. I have also made some
progress in it and also know how to approach it. But I am a little bit

as how to do it in Lex and Yacc. What I have in mind is to
make 2 passes.

During the first pass, I will get associate the labels to the PC
(Prog. Counter) value and during the second pass assemble all the
instructions and for the Branch instructions assemble using the PC
values from the first pass. For this I have to open the same file
twice and parse it using lex and Yacc.

Whats happening here is I have assigned a variable in a header file
(say prc_defines.h) named static unsigned int Firstpass (This is the
flag I am using in my program). This .h file is included in main.c and
asm.y. Everything is fine and good during the first pass. It
associates the label to PC. But during the second pass the I change
the Firstpass (flag) to zero which signifies that it is not the first
pass and still, it works as though the it is the firstpass. I
understand (guess) the yyparse() initializes the variable defined
inthe prc_defines.h to 1 which makes it to behave like a first pass.
See the value changed in the main.c is overridden inside the asm.y.
Any thoughts, help as how to solve this puzzle in lex and yacc.

Any help is greatly appreciated. Thanks in advance.

Regards
Hari.
[Look at the generated yyparse(), debug it like any other C code. -John]

Toby Thain

2004-04-04, 4:37 pm

harisriniv@yahoo.com (Hari Sriniv) wrote
> I have some rudimentary question with the Lex and Yacc. I have been
> developing an assembler for the in house processsor. I have assembled
> the normal instructions pretty easily using the lex and Yacc. I have
> some challenges for the branch instructions. I have also made some
> progress in it and also know how to approach it. But I am a little bit
>

as how to do it in Lex and Yacc. What I have in mind is to
> make 2 passes.
> ...

For what it's worth, my 2-pass assembler for PDP-8 and DG Nova uses
lex and yacc. The first pass defines the labels and the second pass
(re-reading the input file) produces the object code. In case it helps
you, GPL source is available at http://www.telegraphics.com.au/sw/#dpa

Toby

Tim Bauer

2004-04-14, 1:31 am

Toby Thain wrote:[color=darkred]
> harisriniv@yahoo.com (Hari Sriniv) wrote
>

You can do this with one pass though lex and yacc with the following
strategy.
Keep 2 lists.
- Valid labels that have been seen.
- Labels that have been "inferred" or referred to. A label that
appears
in a branch instruction, but has not been seen.

Whenever you see a label in a branch statement.
Either: It is in the set of identified labels you can link it in
and resolve it (ie. relative address or AST or whatever you
are using).

Or: The label is added to the set of labels that need to be resolved
sometime later. These labels need to have a list of instructions
that refer to them so you can backpatch later (when you find the
label).

Whenever you see a valid label declaration.
- Add it to your list of valid labels.
- Scan the list of "inferred" labels and see if any branch
instructions are waiting for its declaration/address and resolve
any of them.

Example (everything except the labels and branches are irrelevant):

... assmbly code
L1: ; a "declared label" label L1
; When you get here, add L1 to your set
; of "declared" or "valid" labels
; additionally you need to see if any prior branches
; referred to this label and resolve them to it if
; necessary.
... assmbly code
JZ B, L2 ; We have not seen "L2" yet so this is an "inferred" label
; or unresolved label. Add it to that set.
... assmbly code
JZ B, L1 ; jump to L1 if B is Zero
; We find L1 in our valid set and can resolve
; it right away.
... assmbly code
JZ A, L2 ; another jump referring to an unknown label.
... assmbly code
L2: ; a declared label
; We add this to our set of valid labels.
; additionally we check and find that 2 earlier branches
; referred to this and fix them up. We can remove them
; from the set of "unresolved" labels now too.

At the end, if your set of unresolved labels is not empty
you can list out the "branches to an invalid label" errors.

Each unresolved label entry needs to keep track of the set of
instructions that referred to them (the line might be nice too
for error reporting). Depending on your data representation, this
can be a relative address or a more abstract "instruction" struct.

The key gain point is that you only need lex and yacc to walk through
your code once and don't need to worry about second passes.

Hope this helps,
- Tim

Sponsored Links