Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1097 > unrolled thread

Best tools for writing an assembler?

Back to article view | Back to comp.compilers

Contents

  Best tools for writing an assembler? tpphysik@gmail.com - 2014-02-18 16:04 -0800
    Re: Best tools for writing an assembler? "C. Bergström" <cbergstrom@pathscale.com> - 2014-02-19 11:14 +0700
    Re: Best tools for writing an assembler? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-02-19 04:25 +0000
    Re: Best tools for writing an assembler? Ivan Godard <ivan@ootbcomp.com> - 2014-02-18 23:23 -0800
      Re: Best tools for writing an assembler? Robert A Duff <bobduff@TheWorld.com> - 2014-02-19 18:20 -0500
        Re: Best tools for writing an assembler? Sébastien Fricker <sebastien.fricker@gmail.com> - 2014-02-21 12:00 +0100
        Re: Best tools for writing an assembler? "BartC" <bc@freeuk.com> - 2014-02-22 00:28 +0000
        Re: Best tools for writing an assembler? noitalmost <noitalmost@cox.net> - 2014-02-23 11:22 -0500
          Re: Best tools for writing an assembler? Sébastien Fricker <sebastien.fricker@gmail.com> - 2014-02-24 07:32 +0100
            Re: Best tools for writing an assembler? Louis Krupp <lkrupp@pssw.com> - 2014-02-24 15:39 -0700
            Re: Best tools for writing an assembler? Ivan Godard <ivan@ootbcomp.com> - 2014-02-24 15:04 -0800
              Re: Best tools for writing an assembler? rpw3@rpw3.org (Rob Warnock) - 2014-02-25 13:00 +0000
            Re: Best tools for writing an assembler? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-02-25 04:09 +0100
          Re: Best tools for writing an assembler? "James Harris" <james.harris.1@gmail.com> - 2014-02-24 23:18 +0000
          Re: Best tools for writing an assembler? noitalmost <noitalmost@cox.net> - 2014-02-27 18:11 -0500
            Re: Best tools for writing an assembler? George Neuner <gneuner2@comcast.net> - 2014-03-01 13:09 -0500
              Re: Best tools for writing an assembler? federation2005@netzero.com - 2014-03-26 17:57 -0700
                Re: Best tools for writing an assembler? federation2005@netzero.com - 2014-04-13 12:24 -0700
    Re: Best tools for writing an assembler? Sébastien Fricker <sebastien.fricker@gmail.com> - 2014-02-19 09:59 +0100
      Re: Best tools for writing an assembler? Robert A Duff <bobduff@shell01.TheWorld.com> - 2014-02-19 18:27 -0500
    Re: Best tools for writing an assembler? Patrik Túri <tpphysik@gmail.com> - 2014-02-20 17:15 -0800
      Re: Best tools for writing an assembler? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-02-21 12:09 +0100
        Re: Best tools for writing an assembler? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-02-24 20:42 +0000
          Re: Best tools for writing an assembler? Ivan Godard <ivan@ootbcomp.com> - 2014-02-24 15:13 -0800
          Re: Best tools for writing an assembler? hu47121@usenet.kitty.sub.org (Hannah) - 2014-02-25 00:43 +0000
            Re: Best tools for writing an assembler? Walter Banks <walter@bytecraft.com> - 2014-02-27 14:14 -0500
          Re: Best tools for writing an assembler? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-02-25 04:23 +0100
      Re: Best tools for writing an assembler? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-02-24 20:35 +0000

Page 1 of 2  [1] 2  Next page →

#1097 — Best tools for writing an assembler?

Hello,

I want to write an assembler for my own processor architecture. It
would be of middle complexity.  What language/tools would you use?
I'm thinking of perl or C++, maybe with some (which?) program library.
What about flex/bison, are those good for this, how hard are they to
use?  Once I have written a very simple assembler in C++, but now I
want more functions and proper error messages as well.  Thank you for
your help.
[An assembler isn't very different from any other compiler except
that the code generator is a lot simpler.  Flex and bison are
well suited for most assembler syntax, write your code in C or C++
as you prefer.  (You can probably guess which book I'd recommend.)
There are some reasonable parser tools for Java, Perl, and python
now which could make sense if you don't need your assembler to run
extremely fast. -John]

[toc] | [next] | [standalone]

#1098

On 02/19/14 07:04 AM, tpphysik@gmail.com wrote:
> I want to write an assembler for my own processor architecture. It
> would be of middle complexity.  ...

I'd recommend to just retarget an existing infrastructure to your arch.

Both of these are c++ with some level of extensibility

(yasm-nextgen fork which is used in production)
https://github.com/path64/assembler

LLVM MC - Create the appropriate tabledefs for your target

[toc] | [prev] | [next] | [standalone]

#1099

tpphysik@gmail.com wrote:

> I want to write an assembler for my own processor architecture. It
> would be of middle complexity.  What language/tools would you use?
> I'm thinking of perl or C++, maybe with some (which?) program library.
> What about flex/bison, are those good for this, how hard are they to
> use?  Once I have written a very simple assembler in C++, but now I
> want more functions and proper error messages as well.  Thank you for
> your help.

The easiest way to write an assembler is to write macros for an
existing macro assembler that will generate the appropriate bytes.
(Assuming memory is byte oriented.)

That also gives you a macro facility without extra work.

You don't say if you need macros, though.

Otherwise, it should be pretty easy with flex/bison.

-- glen

[toc] | [prev] | [next] | [standalone]

#1100

On 2/18/2014 4:04 PM, tpphysik@gmail.com wrote:
> I want to write an assembler for my own processor architecture. It
> would be of middle complexity. ...

I strongly recommend the approach we took in the Mill assembler: we
use the C++ compiler as the first pass, then execute the resulting
program as the second pass. You write a C++ function for each machine
operation: "add(regNum r1, regNum r2)" or whatever. The bodies of each
of these call the emitters with the bit pattern to use, and the
emitters pack the bits into the output.

Note that the C++ forms the meta-language which is traditionally a macro
language. Thus you can rite:
  for(int i=0; i < 8; ++i)
      store(b+4*i, regs[i]);
and get the eight stores to flush your registers.

We actually generate all the function definitions from our specification
machinery, but you can wrte them by hand too, and the work will still be
much less than writing, debugging and documenting a traditional assembler.

[toc] | [prev] | [next] | [standalone]

#1102

Ivan Godard <ivan@ootbcomp.com> writes:

>...we use the C++ compiler as the first pass, then execute the resulting
> program as the second pass. You write a C++ function for each machine
> operation: "add(regNum r1, regNum r2)" or whatever.

Good idea, except I'd write it in Ada or OCaml or something.  I've
done something similar.

You can do all sorts of powerful things this way, because you have the
full power of C++ (or whatever) at your fingertips.

And if you want to write a compiler for some higher-level language, it
can call those same "add" routines.  I've never liked the compiler
design that has the compiler generate assembly language as text, and
then feed that text to a traditional assembler (even though I've
written such compilers).  It seems needlessly inefficient.  The only
sensible argument in favor of that is that it's the only way to ensure
that the assembler and the compiler agree on all the bit-wise
encodings of op-codes and so forth.  In other words, it's the only way
to sufficiently test the assembler (since nobody writes large amounts
of assembly by hand anymore).

But your idea here solves that problem nicely -- there IS no assembler
in the tradition sense.  Just the "add" and so forth routines.

- Bob

[toc] | [prev] | [next] | [standalone]

#1105

On 20/02/2014 00:20, Robert A Duff wrote:
> Ivan Godard <ivan@ootbcomp.com> writes:
>
>> ...we use the C++ compiler as the first pass, then execute the resulting
>> program as the second pass. You write a C++ function for each machine
>> operation: "add(regNum r1, regNum r2)" or whatever.
>
> Good idea, except I'd write it in Ada or OCaml or something.  I've
> done something similar.
>

This is certainly the most important decision.
The tools/language used cannot be switched during the development.

I wrote a parser for C++ code in C and Flex/Bison. Due to the
difficulty to program complex C code, I have migrated my code to C++.
The code get 20% smaller (due to all free() and low level functions
which are no more necessary) and the code get easier to understand.
The STL contains was also permitting to implement high level
optimization and also reducing the complexity of the algorithms. Doing
this in C is more difficult.

Now, I would write the same in OCaml because:
 - The type checking is very good
 - Menhir (replacement of Flex/Bison) exists
 - The source code would be smaller without syntax glue (like the
necessity to have heaer, ....)
 - Easy possibility to program complex algorithm in few lines.
 - The OCaml code is only 2 times slower that C code (which is acceptable)
 - The startup code (time nead to reach main) is similar to C++.

But migrating an existing project is not possible.
In other words: it makes sense to take time to choose the right
framework at the beginning.

[toc] | [prev] | [next] | [standalone]

#1107

"Robert A Duff" <bobduff@TheWorld.com> wrote in message
> Ivan Godard <ivan@ootbcomp.com> writes:
>
>>...we use the C++ compiler as the first pass, then execute the resulting
>> program as the second pass. You write a C++ function for each machine
>> operation: "add(regNum r1, regNum r2)" or whatever.
>
> Good idea, except I'd write it in Ada or OCaml or something.  I've
> done something similar.
>
> You can do all sorts of powerful things this way, because you have the
> full power of C++ (or whatever) at your fingertips.
>
> And if you want to write a compiler for some higher-level language, it
> can call those same "add" routines.  I've never liked the compiler
> design that has the compiler generate assembly language as text, and
> then feed that text to a traditional assembler (even though I've
> written such compilers).  It seems needlessly inefficient.

I've gone the other way, from generating machine code (or my own
object code) directly, to now generating assembly source code. Then I
can leave all that side of it to (in my case) NASM, to worry about
object and executable file formats, and instruction encodings.

The inefficiency is not really an issue any more (for inefficient and
bloated text files try HTML and XML).

If the resulting code was not needed for a standalone executable or
for libraries, then maybe a function-based scheme could work well,
although to examine the output, you might still want a familiar
assembly-like text format.

--
Bartc

[toc] | [prev] | [next] | [standalone]

#1109

Since it hasn't come up in the discussion, I'd like to mention linking
and loading. You should at least be aware of what they do, especially
the loader.

I wouldn't bother with any generation tools like flex or bison, unless
you want to gain experience with those tools for some other project.
Since it's your own architecture, which has no native tools, you'll be
cross-compiling so speed of the assembler won't matter. It'll be a
long time before you write a program for your architecture that'll
take longer than a second to compile, even if you use Perl. So the
language you use should be the one you know best.  My bias is toward
C++, but it really won't matter in your case.

I think that by hand-writing your own scanner and parser, you'll get
to know your assembly syntax better. And unless you have something
really strange, simple recursive descent will work fine for the
parser.

First, just get something that works for a simple assembly program.
That'll give you the encouragement to add a few more features. Then
you're off and running.

[toc] | [prev] | [next] | [standalone]

#1110

On 23/02/2014 17:22, noitalmost wrote:
>
> I wouldn't bother with any generation tools like flex or bison, unless
> you want to gain experience with those tools for some other project.
> Since it's your own architecture, which has no native tools, you'll be
> cross-compiling so speed of the assembler won't matter. It'll be a
> long time before you write a program for your architecture that'll
> take longer than a second to compile, even if you use Perl. So the
> language you use should be the one you know best.  My bias is toward
> C++, but it really won't matter in your case.
>
> I think that by hand-writing your own scanner and parser, you'll get
> to know your assembly syntax better. And unless you have something
> really strange, simple recursive descent will work fine for the
> parser.
>

Sorry, but even if Flex/Bison are difficult to setup, writing a parser
by hand is not a good way to work.
Tools like Flex/Bison give several advantages that you cannot cover by
writing a parser by hand:
 1) They are able to manage complex rules which would need many lines of
code. For example, parsing an integer consists only of matching the
regular expression pattern "[0-9]+". It is simple and more readable than
writing directly its C++ code.
 2) The generated code is optimized at a level different to what the
compiler does. For example, if in your keyword you have "visual" and
"virtual", the generated code will first match "vi" and then "rtual" or
"sual". Of course writing such optimization by hand is practically not
possible.
 3) Flex/Bison are performing some error analysis which permits detect
unused rules, unreachable states, ... All this checks are not existing
for hand written parser. That's mean that your test suite need to handle
such kind of non detected errors.
 4) Inserting a new keyword/extending a syntax of an existing parser is
more safe. In fact, due to all checks make by the parser generator, if
the code compiles without bison/flex warnings you can be sure that your
new syntax extension does not collide with the existing one. In other
words, you did not program a regression my extending your syntax.

In other words, saying that writing parser by hand is better is the same
as saying "why using object oriented programming? I can do the same in C
with struct!" Yes, but the result is less readable, the compiler does
does less verifications.
[Yacc or bison provides the pleasant assurance that the langauge your
program parses is exactly the one in the grammar, and not some
superset due to missing error checks. -John]

[toc] | [prev] | [next] | [standalone]

#1113

On Mon, 24 Feb 2014 07:32:37 +0100, Sibastien Fricker
<sebastien.fricker@gmail.com> wrote:

>On 23/02/2014 17:22, noitalmost wrote:
>>
>> I wouldn't bother with any generation tools like flex or bison, unless
>> you want to gain experience with those tools for some other project. ..

>Sorry, but even if Flex/Bison are difficult to setup, writing a parser
>by hand is not a good way to work. ...

Everyone should hand-write a lexer and parser ... once.  If you're
designing the language syntax as you go, you'll design something
that's easy to scan and parse.  I agree with noitalmost that recursive
descent is the way to go.

Louis

[toc] | [prev] | [next] | [standalone]

#1114

> Sorry, but even if Flex/Bison are difficult to setup, writing a parser
> by hand is not a good way to work.
> Tools like Flex/Bison give several advantages that you cannot cover by
> writing a parser by hand: ...

> In other words, saying that writing parser by hand is better is the same
> as saying "why using object oriented programming? I can do the same in C
> with struct!" Yes, but the result is less readable, the compiler does
> does less verifications.
> [Yacc or bison provides the pleasant assurance that the langauge your
> program parses is exactly the one in the grammar, and not some
> superset due to missing error checks. -John]

Well, not really.

You see, there is more to a parser (and a lexer; you seem to be
conflating the two) than parsing. It is rather rare for a parser to
receive a syntactically correct program as input; errors are more
common than correct code. So the parser has not only to recognize
correct sentences, it must do something useful with incorrect ones.
"Syntax error: right-reduction stack underflow" is not useful.

You can avoid the problem by introducing error states into your
grammar.  Unfortunately, it turns out that LR and LALR parsing is not
the way natural languages work (German possibly excepted), and a
reasonably complete set of useful error states produces a hopelessly
unmaintainable generated parser, or blows the generation.

Programming languages, even assembler, have always tended to be LL(1)
to a first approximation. As a result, production compilers intended
for use by those unfamiliar with the internals have tended to be LL(1)
too, and usually recursive descent. The advantage of RD is that the
semantics can be done on the fly, and the semantics can be used to
guide the parse when the actual language is not a CFG (and most of
them are not, to at least some degree) without exponential explosion
of state.

In contrast, a parser-generator only gets you a syntax tree. You still
must walk the tree doing semantics and real work - and guess what,
that tree walker is the same code you had to write for a RD parser,
but the RD parser didn't require you to deal with an inhumane tool. In
short, YACC (and Bison) looked like a good idea, and are in fact
usable for toy languages and student exercises, but don't use them for
real work.

That's for parsers. Lexers are a different matter. First rule: never
use a parser for what a lexer would do. Your language description (for
the parser) should never take terminal productions to the character
level.  Think about what your combined-lex-and-parse grammar looks
like if you want it to accept UTF16 or Danish keyboards - again,
issues that don't come up in toys, but matter very much in real
software.

Secondly: as a rough rule of thumb, of all the work done by a compiler
at -O0, half will be in the lexer - it's the only place where work is
done character-by-character and not at a coarser granularity like
lexeme; there are *many* more characters in a program than lexemes.
Consequently efficiency of execution matters in the lexer, and
generated lexers of the Flex sort are very inefficient. Sure, the
state transitions look efficient, but you haven't thought about cache
behavior, nor about copy costs, symbol table look-up and so on. If
your lexer isn't doing that work too then all it is is a keyword
detector, whereas it should be very much more.

A good lexer will look at each character exactly once to do everything
including to isolate the containing lexeme, to find a symbol table
entry for it (including program declared symbols, not just keywords).
and to enter the symbol in the symbol table if it's not been seen
before. Once!  Kudos if your lexer, on encountering a bogus lexeme,
can find the nearest misspelling currently in the symbol table, emit a
diagnostic, and proceed with the assumed correction.

You may feel that modern machines are fast enough that lexer (and
compiler) performance doesn't matter. If so you are right, for toys;
toys in this context include programs with < 100KLOC. Real programs,
needing real compilers, start at > 1MLOC and go up quite a ways from
there. And only toys can use separate compilation to avoid compile
time; production test and verification recompile the World from
scratch source. Frequently. Of course, test and verification are not
common in toys.


Just my opinion, mind you, albeit an opinion based on 11 compilers I
have done over the years, for a variety of languages and targets. Your
mileage may vary.

[toc] | [prev] | [next] | [standalone]

#1120

Ivan Godard  <ivan@ootbcomp.com> wrote:
+---------------
| Programming languages, even assembler, have always tended to be LL(1)
| to a first approximation. As a result, production compilers intended
| for use by those unfamiliar with the internals have tended to be LL(1)
| too, and usually recursive descent. The advantage of RD is that the
| semantics can be done on the fly, and the semantics can be used to
| guide the parse when the actual language is not a CFG (and most of
| them are not, to at least some degree) without exponential explosion
| of state.
+---------------

Plus, there's a useful trick I learned from the BLISS-10 compiler,
which is that you can very easily embed a simple operator precedence
parser into a recursive descent parser, simply by giving keywords and
flow-control operators [IF, CASE, etc.] very high operator precedences
and "stoppers" [commas, semicolons, right brackets, FI, ESAC, etc.]
very low precedences. This enables a recursive descent parser to
handle complex arithmetic expressions without ending up with long
chains of (otherwise useless) reductions in the parse graph.

I've found this combination to be very convenient, and have used it a
number of times over the years when a small DSL was needed, e.g., for
a user interface or as part of a software build system.


-Rob

p.s. More detail on this construct, including some sample code
[in Scheme], can be found in a couple of previous articles here
from 2010, subject "Re: Is that difficult to write a Shift-Reduce
parser", see:

http://compilers.iecc.com/comparch/article/10-05-014
http://compilers.iecc.com/comparch/article/10-05-037

-----
Rob Warnock		<rpw3@rpw3.org>
627 26th Avenue		<http://rpw3.org/>
San Mateo, CA 94403

[toc] | [prev] | [next] | [standalone]

#1118

Sibastien Fricker schrieb:

>> I think that by hand-writing your own scanner and parser, you'll get
>> to know your assembly syntax better. And unless you have something
>> really strange, simple recursive descent will work fine for the
>> parser.
>>
>
> Sorry, but even if Flex/Bison are difficult to setup, writing a parser
> by hand is not a good way to work.
> Tools like Flex/Bison give several advantages that you cannot cover by
> writing a parser by hand:
[...]

With an LL grammar it's not a big problem to write a recursive-descent
parser by hand. LL grammars also can be written in EBNF, which
typically results in both shorter and better readable/writeable
grammars (and parsers?). Also the (grammars for) recursive descent
parsers are easier to debug than table-driven parsers.

This IMO makes it safe enough to write LL parsers by hand. Grammar
checks then are performed by the compiler (for missing productions) and
linker (for unreachable productions).

> In other words, saying that writing parser by hand is better is the same
> as saying "why using object oriented programming? I can do the same in C
> with struct!" Yes, but the result is less readable, the compiler does
> does less verifications.

Which verifications do you have in mind? A compiler cannot check the
validity of an table driven lexer or parser, it only can find
syntactical errors in the generated code. Such errors either result from
a buggy generator, in which case you had to fix the generator yourself
or wait for bug fixes by its maintainer. Or they result from syntax
errors in the semantic code of the grammar, which have to be fixed anyhow.

> [Yacc or bison provides the pleasant assurance that the langauge your
> program parses is exactly the one in the grammar, and not some
> superset due to missing error checks. -John]

Grammars often (typically?) are supersets of a language, with semantic
checks added manually to the parser code. Using an parser generator does
not assure anything about sub-/supersets, then. This also makes it very
hard to switch the implementation language for such a grammar, because
the generated lexer and semantic code is encoded in a specific language.
I'm still waiting for an parser generator creating code for a different
or multiple implementation languages, from the same grammar.

That's not a big problem with languages *not* intended for the
generation of executable code (file format parsers...), but when you
ever want to develop an compiler *in* your new language, you have to
translate the entire parser generator and the grammar into that language
as well.


I've used (and sometimes modified) several parser generators myself, and
found only one goodie with them: an (interactive) grammar debugger like
in MetaS or TextTransformer. Such extensions IMO contribute much more to
the development of an language-conforming grammar than the use of an
mere lexer/parser code generator.

DoDi

[toc] | [prev] | [next] | [standalone]

#1116

"noitalmost" <noitalmost@cox.net> wrote in message


> I wouldn't bother with any generation tools like flex or bison, unless
> you want to gain experience with those tools for some other project.

IMO this is very valid. My own experience was that writing a compiler by
hand (albeit using a language with inbuilt RE handling) was much easier than
using some of the popular tools. And the hand-written nature of the parser
helped produce good error messages.

It wouldn't have worked without some basic rules being established and for
sure they were hard to decide on. But once in place the rest of it was
easier. If it's of help to the OP I wrote it up in a fairly long post at

  https://groups.google.com/d/topic/comp.lang.misc/ZsdLITOXL-w/discussion

It was for a compiler but the points should apply well to an assembler too.

James

[toc] | [prev] | [next] | [standalone]

#1122

On Monday, February 24, 2014 01:32:37 AM Sibastien Fricker wrote:
> Sorry, but even if Flex/Bison are difficult to setup, writing a parser
> by hand is not a good way to work.
> Tools like Flex/Bison give several advantages that you cannot cover by
> writing a parser by hand:
>  1) They are able to manage complex rules which would need many lines of
> code. For example, parsing an integer consists only of matching the
> regular expression pattern "[0-9]+". It is simple and more readable than
> writing directly its C++ code.

But you have to understand the grammar of those rules as expressed in
the scanner/parser tools. Until you've learned those tools, the C++
code will be more understandable to you, even if it's expressed more
verbosely. Readability is somewhat subjective and depends a lot on
what you're familiar with. You can do some pretty cool stuff in Latin
with only a word or two, but if you don't know Latin, the 15-word,
2-sentence English translation is much more readable.  (I'm assuming,
of course, that you understand English, and aren't one of those crazy
monkeys with the typewriter that can generate Shakespearean sonnets.
:)

>  2) The generated code is optimized at a level different to what the
> compiler does. For example, if in your keyword you have "visual" and
> "virtual", the generated code will first match "vi" and then "rtual" or
> "sual". Of course writing such optimization by hand is practically not
> possible.

But this is the OP's first attempt at a relatively robust assembler.
Have you forgotten your first significant project? When the magical
feelings were "It works!" and "I know how it works!" rather than "I
saved a microsecond in assembly time!"

>  3) Flex/Bison are performing some error analysis which permits detect
> unused rules, unreachable states, ... All this checks are not existing
> for hand written parser. That's mean that your test suite need to handle
> such kind of non detected errors.

Very true, but we are talking about assembler syntax here.

>  4) Inserting a new keyword/extending a syntax of an existing parser is
> more safe. In fact, due to all checks make by the parser generator, if
> the code compiles without bison/flex warnings you can be sure that your
> new syntax extension does not collide with the existing one. In other
> words, you did not program a regression my extending your syntax.
>
> In other words, saying that writing parser by hand is better is the same
> as saying "why using object oriented programming? I can do the same in C
> with struct!" Yes, but the result is less readable, the compiler does
> does less verifications.

I don't think that's a valid comparison. To the new user, it's more
the reverse than anything. Until you've used a parser tool for quite a
while, it's like a giant black box. The scanner tool is a smaller
black box. But rather than a nice OOP class, it's more like the
structs of Win95 MFC. You have to understand a lot about the global
organization, plus a lot of implementation details, and you have 2
extra grammars to learn. In other words, you have to understand a lot
of stuff before you understand anything at all. I just don't think
it's worth it for assembler syntax. There's a good chance the OP will
just give up, frustrated and completely mystified. If we were talking
about parsing Perl syntax, that would be different. Or if the OP were
writing 10 assemblers, that would be different too.

I'm obviously not an expert in this field, and my experience in
compiler writing is rather slim. It consists of 3 not overly
sophisticated assemblers and 2 toy HLL compilers. My experience with
the frustration of "shift/reduce conflict" however, is of some value
here, I think.

And I don't mean to denegrate the value of any of the parser tools.
But they're only easy to use and integrate into your compiler once
you've learned how to use them, which isn't trivial.

[toc] | [prev] | [next] | [standalone]

#1124

I keep expecting to see Chris Clark jump in here.  8-)


On Thu, 27 Feb 2014 18:11:28 -0500, noitalmost <noitalmost@cox.net>
wrote:

>... you have to understand the grammar of those rules as expressed in
>the scanner/parser tools. Until you've learned those tools, the C++
>code will be more understandable to you, even if it's expressed more
>verbosely. Readability is somewhat subjective and depends a lot on
>what you're familiar with.

That's true of any tool.

However, parsers are notoriously difficult to get correct: it's not
enough that your parser recognizes the language, it also has to reject
everything else.  That can be quite hard to verify.

Keep in mind that there are both LR and LL parser tools.  LR tools
produce table driven state machines, but LL tools produce recursive
decent code that can be read and (fairly) easily understood.

I would steer the OP to something like ANTLR instead of Bison/Flex.
ANTLR even has a (separate) GUI that displays syntax diagrams for the
grammar and you can test your grammar within the GUI without needing
to write a program.
[Only caveat is the ANTLR tool requires Java to run.  It does *not*
require that _your_ program also be written in Java - it can generate
parsers and lexers in several languages.]


>Have you forgotten your first significant project? When the magical
>feelings were "It works!" and "I know how it works!" rather than "I
>saved a microsecond in assembly time!"

Using a parser tool initially is more about correctness than about
saving time.  Time savings come with ongoing maintenance, if any.


>Sibastien Fricker wrote:
>>  3) Flex/Bison are performing some error analysis which permits detect
>> unused rules, unreachable states, ... All this checks are not existing
>> for hand written parser. That's mean that your test suite need to handle
>> such kind of non detected errors.
>
>Very true, but we are talking about assembler syntax here.

Assembler still can be pretty complex.  I've used assemblers that had
C like expression syntax.


>Until you've used a parser tool for quite a while, it's like a giant
>black box. The scanner tool is a smaller black box.

And a C++ compiler isn't a giant black box?


>You have to understand a lot about the global organization, plus a
>lot of implementation details, and you have 2 extra grammars to learn.
>In other words, you have to understand a lot of stuff before you
>understand anything at all.

This is a valid concern, but IMO it is exaggerated.  In a day or so
you can learn enough about the tool to begin working in earnest.  Most
projects will never need the more complicated options provided by the
tool and those can be learned as you go.

Bison in particular has a complicated set of options ... which, again,
is why I would start with a different tool.  Learn Bison if and when
you need to.


>I'm obviously not an expert in this field, and my experience in
>compiler writing is rather slim. It consists of 3 not overly
>sophisticated assemblers and 2 toy HLL compilers. My experience with
>the frustration of "shift/reduce conflict" however, is of some value
>here, I think.

LL tools don't have mysterious shift/reduce, reduce/reduce conflicts.
The learning curve for LL tools is much shallower.


>And I don't mean to denegrate the value of any of the parser tools.
>But they're only easy to use and integrate into your compiler once
>you've learned how to use them, which isn't trivial.

No use of any compiler/generator is "trivial" - it all requires some
level of understanding, both of the tool and it's expected input.

YMMV,
George

[toc] | [prev] | [next] | [standalone]

#1188

On Saturday, March 1, 2014 12:09:39 PM UTC-6, George Neuner wrote:
> However, parsers are notoriously difficult to get correct: it's not
> enough that your parser recognizes the language, it also has to reject
> everything else.  That can be quite hard to verify.

That's not been my experience. But then, I use a formalism and
calculus for "context free expressions", which makes the whole affair
rather transparent and easy. I wouldn't worry too much about the
syntax end of the project (particularly after properly attending to
the "normalization" process alluded to below). The real issues are
going to be the rest of the assembler!

If one is going to do an assembler -- as I'm getting fixed to do --
there are a few words that should be said on the matter.

First in terms of the syntax, the best advice is to *normalize* the
syntax.  Lately, I've seen a trend in the design of languages that can
only be described as a retreat to the 1960's back when people thought
you could (or should) get a grammar to engulf the entire set of
semantic constraints, not just the enveloping syntax. The mindset runs
so deep in those rooted in that era, that it may even be done
unconsciously, rather than by intent.

The specific example I have in mind is C++ at the high level (and even
C with its false separation of syntaxes for "direct" and "abstract"
declarators). At the assembly level, the most notorious example is
MASM and the Intel syntax it is associated with.

There are a half-dozen instances of the phrase category "Directive" in
the phrase structure grammar whose only distinctions are semantic in
nature: i.e.  there is an attempt to implement semantic constraints by
cleaving this single category into a half-dozen shards.

A good grammar should serve as nothing more than an enveloping
framework.  Leave the constraints out of the grammar. That's what the
{...} in Yacc are for (for instance) if you're using Yacc. If, on the
other hand, you're STARTING with MASM like syntax, then a good
exercise is to first try to NORMALIZE the syntax, by (a) recombining
the various instances of duplicated categories and (b) factoring out
the constraints.

In many cases, one may find that the "cosntraints" are not actually
needed at all, and one can then generalize to create a more powerful
and robust (and simpler) language.

As it turns out, I actually carried out the process of
normalization(!). It would be lengthy to post results here, though the
resulting grammar is not particularly large. Both the syntax for
directives and expressions have been normalized. Part of this,
interestingly, was already attempted by Microsoft in their old MASM
reference, where they indexed the "expression" category by precedence
level, rather than concocting separate names for all the instances of
expression type. But they still left out the boolean expressions from
the rest of the syntax.

On the design end, the best thing to do is first do a survey of all
the assemblers in common use out there, particularly ones that claim a
degree of platform-universality. GAS works with a large number of
platforms, for instance, and implements the AT&T syntax. Both MASM and
NASM work with the large family of x86 processors, though there is a
fairly large portion of the language in the syntax for directives
(especially in the case of NASM) that can be made largely
CPU-independent.

In the process of surveying, there should be careful attention paid to
the "history" notes to see how the items evolved and what roadblocks
were encountered. You'll be encountering the same roadblocks. GAS, by
the way, has several huge history lists in its distribution.

As far as CPU-independence goes: even if you're targeting for a single
CPU, you still need to have some level of robustness for
CPU-independence. The reason is simple: as of late, CPU's have been
undergoing an increasingly rapid series of incremental changes (even
the lowly 8-bit 8052 which now has a 32 bit version!) If you're stuck
in the present (a mindset you can always identify by those people who
use "modern" to describe contemporary notions or ideas), you're going
to quickly be stuck in the past with that CPU.

So, there should always be some attention to keeping the particulars
of the CPU as much out of the assembler as possible.

The same goes for the back end. Object formats have also been
undergoing changes as of late. There should be reconfigurability for
both this and even the processor model and input syntax (e.g. by ways
of dot-keyword directives like ".att" for AT&T syntax or ".P6" for
Pentium Pro, "elfx32" for ELFx32 object format etc.)

That's where all your worry's going to be. Not the syntax!

[toc] | [prev] | [next] | [standalone]

#1218

On Wednesday, March 26, 2014 7:57:11 PM UTC-5, federat...@netzero.com wrote:
> First in terms of the syntax, the best advice is to *normalize* the
> syntax. At the assembly level, the most notorious example [of an
> unnormalized syntax] is MASM and the Intel syntax it is associated with.

> There are a half-dozen instances of the phrase category "Directive" in
> the phrase structure grammar whose only distinctions are semantic in
> nature: i.e.  there is an attempt to implement semantic constraints by
> cleaving this single category into a half-dozen shards.

In fact, based on the reference for MASM 6.1, one could "reintegrate" the
directive syntax by first classifying all their contexts:

Contexts:
(a) RunTimeLoop: inside a .WHILE/.REPEAT statement group

(b) MacroBody: inside a MACRO/REPT/REPEAT/WHILE/FOR/FORC/IRP/IRPC statement
group

(c) Statement: inside a .IF/.ELSEIF/.ELSE statement group, a statement group
headed by any of the IF*/ELSEIF*/ELSE keywords or at the TopLevel

(d) SegmentBody: inside a statement group (1) begun by a ".CODE", ".DATA",
".DATA?", ".CONST", ".FARDATA", ".FARDATA?", ".STACK" or "SEGMENT" directive
and ended by its matching "ENDS" directive; or (2) begun by a "PROC" directive
and ended by its matching "ENDP" directive.

(e) Inside a statement group headed by STRUC/STRUCT/UNION

Then it suffices to lay out one (large) set of phrase structure rules for the
directives ("Dir"), with the constraints then noted separately. It's much
easier for a parser to check for these constraints than to try and force-fit
it into the grammar. In addition, organizing things this way may lead to
simplifications that occur by recognizing that some of the constraints are
simply not needed and can be removed.

Notice, by the way, in the list below that the assembler does
"quasi-compilation" (that is, it compiles run-time statements for loops and
functional calls). I don't know if GAS is doing that much. But a decent
assembler might have to match this level of functionality.

For MASM syntax, the classification would lead to the following groups.

(1) Loop directives appear only in context (a) and include phrase structure
rules for:
Dir -> ".BREAK" ...
Dir -> ".CONTINUE" ...

(2) Macro Directives appear only in context (b) and include directives for the
prefix ":", "GOTO" and "EXITM".

(3) Segmentation Directives appear only in contexts (a), (b) or (c) and
involve all the ".CODE", ..., "SEGMENT" "segment body" directives

(4) In-Segment Directives appear only in context (d) and include the
mnemonics, along with the x86 specific prefixes (i.e. "REP", "REPE", ...,
"LOCK").

It also includes the quasi-compiled control-flow (yes, MASM is doing basic
compilation!):

".IF"...".ELSEIF"...".ELSE"...".ENDIF",
".WHILE"...".ENDW"
".REPEAT"...".UNTIL" (or ".UNTILCXZ")
"PROC"..."ENDP"

as well as ".STARTUP", ".EXIT", "LABEL" "INVOKE" (the "invoke" statement is
the quasi-compiled function call).

(5) Member Directives appear only in context (e): the "STRUC", "STRUCT" and
"UNION" statements.

(6) Type and Alignment Directives appear in contexts (d) and (e). Those are
the:
initializers ("DB", "DW", ...)
type declarations ("BYTE", "SBYTE", "WORD", ...)
type declarations involving "typedef"'ed types
declarations that include structure/union field components
declarations involving "record" typenames
alignment/location directives ("EVEN", "ORG", "ALIGN")

(7) General Directives may appear in all contexts.
(Basically, every other directive in the MASM 6.1 syntax).

[toc] | [prev] | [next] | [standalone]

#1101

If starting from scratch I would use a high level language and for
performance reasons not perl. An assembler may need to assemble big
sources and so it should be as fast as possible.  Also think about the
start time of your assembler: if you write it in C#, loading all the
.NET framework may need a lot of time, in this case your assembler may
need 20s before your main function get reached.

If writing from the scratch, I would use OCaml. OCaml provides
ocamllex/ocamlyacc (and also menhir which is also a lex/yacc
replacement) which are quite similar to flex/bison. I think that
coding in ML would permits to get a smaller source file and easier to
read.  But of course you need to learn a new programming language...
See http://caml.inria.fr/pub/docs/oreilly-book/html/book-ora107.html
for an ocamllex/ocamlyacc sample.

[toc] | [prev] | [next] | [standalone]

#1103

Sibastien Fricker <sebastien.fricker@gmail.com> writes:

> If starting from scratch I would use a high level language and for
> performance reasons not perl. An assembler may need to assemble big
> sources and so it should be as fast as possible.

I don't agree -- nobody writes big assembly sources by hand these
days.  Maybe you're thinking of compiler-generated assembly,
but I think compilers should generate machine language, not
assembly language.  I like Ivan Godard's idea better.

> If writing from the scratch, I would use OCaml.

That's a good choice, but...

>...OCaml provides
> ocamllex/ocamlyacc (and also menhir which is also a lex/yacc
> replacement) which are quite similar to flex/bison.

...but I'd use Ivan Godard's idea, thus avoiding any need for
horsing around with lexing and parsing.

>...I think that
> coding in ML would permits to get a smaller source file and easier to
> read.  But of course you need to learn a new programming language...
> See http://caml.inria.fr/pub/docs/oreilly-book/html/book-ora107.html
> for an ocamllex/ocamlyacc sample.

Well, learning a new programming language is generally a good idea,
and fun, especially if that language has interesting ideas.

- Bob

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.compilers

csiph-web