Re: Lex and Yacc Newbie Questions!!!

Toby Thain wrote:
> 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
>>confused as how to do it in Lex and Yacc. What I have in mind is to
>>make 2 passes.
>>...


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

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