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

Groups > comp.lang.c > #141120 > unrolled thread

[PC] Simple AST

Back to article view | Back to comp.lang.c

Contents

  [PC] Simple AST luser droog <luser.droog@gmail.com> - 2019-02-16 14:23 -0800
    Re: [PC] Simple AST BGB <cr88192@hotmail.com> - 2019-02-19 15:14 -0600
      Re: [PC] Simple AST luser droog <luser.droog@gmail.com> - 2019-02-19 19:51 -0800
        Re: [PC] Simple AST Rosario19 <Ros@invalid.invalid> - 2019-02-20 09:28 +0100
          Re: [PC] Simple AST "Pascal J. Bourguignon" <pjb@informatimago.com> - 2019-02-20 09:39 +0100
            Re: [PC] Simple AST Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-03-06 08:34 -0800
              Re: [PC] Simple AST "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-06 09:02 -0800
                Re: [PC] Simple AST "I Set My Girlfriend's Pantyhose on Fire" <cdalten@gmail.com> - 2019-03-06 11:14 -0800
                Re: [PC] Simple AST Ian Collins <ian-news@hotmail.com> - 2019-03-07 14:11 +1300
                  Re: [PC] Simple AST "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-06 17:48 -0800
                    Re: [PC] Simple AST Ian Collins <ian-news@hotmail.com> - 2019-03-07 15:21 +1300
                      Re: [PC] Simple AST luser droog <luser.droog@gmail.com> - 2019-03-06 18:28 -0800
                        Re: [PC] Simple AST luser droog <luser.droog@gmail.com> - 2019-03-06 18:37 -0800
                      Re: [PC] Simple AST "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-06 18:47 -0800
                        Re: [PC] Simple AST luser droog <luser.droog@gmail.com> - 2019-03-06 18:53 -0800
              Re: [PC] Simple AST "Pascal J. Bourguignon" <pjb@informatimago.com> - 2019-03-06 18:38 +0100
                Re: [PC] Simple AST Keith Thompson <kst-u@mib.org> - 2019-03-06 09:53 -0800
                  Re: [PC] Simple AST "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-06 09:59 -0800
                  Re: [PC] Simple AST "Pascal J. Bourguignon" <pjb@informatimago.com> - 2019-03-06 19:49 +0100
                    Re: [PC] Simple AST Bart <bc@freeuk.com> - 2019-03-06 19:23 +0000
                      Re: [PC] Simple AST David Brown <david.brown@hesbynett.no> - 2019-03-06 23:29 +0100
                      Re: [PC] Simple AST BGB <cr88192@hotmail.com> - 2019-03-06 21:54 -0600
                        Re: [PC] Simple AST James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-03-08 18:52 -0500
                          Re: [PC] Simple AST "Pascal J. Bourguignon" <pjb@informatimago.com> - 2019-03-09 01:56 +0100
                            Re: [PC] Simple AST Keith Thompson <kst-u@mib.org> - 2019-03-08 18:22 -0800
                              Re: [PC] Simple AST David Brown <david.brown@hesbynett.no> - 2019-03-09 14:02 +0100
                                Re: [PC] Simple AST Keith Thompson <kst-u@mib.org> - 2019-03-09 12:20 -0800
                                  Re: [PC] Simple AST David Brown <david.brown@hesbynett.no> - 2019-03-10 00:04 +0100
                            Re: [PC] Simple AST Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-09 02:28 +0000
                          Re: [PC] Simple AST BGB <cr88192@gmail.com> - 2019-03-08 23:06 -0600
                      Re: [PC] Simple AST Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-03-12 23:06 -0700
                        Re: [PC] Simple AST Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-03-14 06:48 +0000
                          Re: [PC] Simple AST James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-03-14 07:14 -0400
                            Re: [PC] Simple AST Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-03-14 14:58 +0000
                              Re: [PC] Simple AST James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-03-14 10:13 -0700
                              Re: [PC] Simple AST Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-03-18 08:34 -0700
                            Re: [PC] Simple AST Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-03-23 10:57 -0700
                              Re: [PC] Simple AST James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-03-25 11:42 -0700
                          Re: [PC] Simple AST Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-03-18 07:18 -0700
                        Re: [PC] Simple AST Bart <bc@freeuk.com> - 2019-03-14 15:34 +0000
                          Divorcing rabbits with Tim R (Was: [PC] Simple AST) gazelle@shell.xmission.com (Kenny McCormack) - 2019-03-14 16:52 +0000
                    Re: [PC] Simple AST Keith Thompson <kst-u@mib.org> - 2019-03-06 22:12 -0800
                      Re: [PC] Simple AST David Brown <david.brown@hesbynett.no> - 2019-03-07 08:54 +0100
                      Re: [PC] Simple AST "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-07 03:20 -0800
                    Re: [PC] Simple AST Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-03-12 23:08 -0700
                  Re: [PC] Simple AST luser droog <luser.droog@gmail.com> - 2019-03-06 14:08 -0800
                    Re: [PC] Simple AST Keith Thompson <kst-u@mib.org> - 2019-03-06 22:13 -0800
                Re: [PC] Simple AST Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-06 19:38 +0000
                  Re: [PC] Simple AST "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-06 11:54 -0800
                    Re: [PC] Simple AST Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-03-07 14:43 +0300
                      Re: [PC] Simple AST "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-07 03:58 -0800
                        Re: [PC] Simple AST David Brown <david.brown@hesbynett.no> - 2019-03-07 13:07 +0100
          Re: [PC] Simple AST Rosario19 <Ros@invalid.invalid> - 2019-02-20 10:35 +0100
      Re: [PC] Simple AST Bart <bc@freeuk.com> - 2019-02-20 14:26 +0000
        Re: [PC] Simple AST BGB <cr88192@hotmail.com> - 2019-02-20 14:32 -0600
          Re: [PC] Simple AST "I Set My Girlfriend's Pantyhose on Fire" <cdalten@gmail.com> - 2019-02-21 13:38 -0800
          Re: [PC] Simple AST Thiago Adams <thiago.adams@gmail.com> - 2019-02-22 04:03 -0800

Page 1 of 3  [1] 2 3  Next page →

#141120 — [PC] Simple AST

Going further with the parser combinator code, I took the example
EBNF grammar for TinyC from 

  https://tomassetti.me/ebnf/

and using a large "swath" of the grammar I'm trying to construct
an Abstract Syntax Tree with my parsers.

This is a draft which compiles, but I have not yet written any 
apparatus to print out the resulting tree. I've tried to make 
the shortest, simplest code to make a somewhat simple tree. The 
tree node structure is simplistic enough that I reuse the same 
data structure for a list which is treated as a stack to build 
up the program tree from smaller trees. Any comments on the 
following code? Is there a shorter and/or simpler way to do it?

Additional files from the same commit "Saturday afternoon"
https://github.com/luser-dr00g/pcomb/archive/6cdd180cf5233aa46ce9f4c0a8ce325b080cbd5f.zip

$ cat pc4eg.c
#include "pc4re.h"
#include "pc4priv.h"

typedef struct token token;
struct token {
  enum { ID, INT, OP, STMT } type;
  char *id;
  int    i;
  char  op;
};

typedef struct tree *tree;
struct tree {
  token value;
  tree next;
  tree first;
};
define_new_function_for_( tree )


void tpush( tree *root, tree node ){
  node->next = *root;
  *root = node;
}
tree tpop( tree *root ){
  tree node = *root;
  *root = node->next;
  node->next = NULL;
  return node;
}
tree last_next( tree t ){ return  t->next  ?  last_next( t->next )  :  t; }
tree last_child( tree t ){ return  last_next( t->first ); }


void make_id( void *p, char *s ){
  tree *t = p;
  tpush( t, new_tree( (struct tree){ (token){ ID, .id = s }, NULL, NULL } ) );
}

void make_int( void *p, char *s ){
  tree *t = p;
  tpush( t, new_tree( (struct tree){ (token){ INT, .i = atoi( s ) }, NULL, NULL } ) );
}

void make_op( void *p, char *s ){
  tree *t = p;
  tree y = tpop( t );
  tree x = tpop( t );
  x->next = y;
  tpush( t, new_tree( (struct tree){ (token){ OP, .op = *s }, NULL, x } ) );
}

void make_expr_stmt( void *p, char *s ){
  tree *t = p;
  tree x = tpop( t );
  tpush( t, new_tree( (struct tree){ (token){ STMT }, NULL, x } ) );
}

void make_empty_stmt( void *p, char *s ){
  tree *t = p;
  tpush( t, new_tree( (struct tree){ (token){ STMT }, NULL, NULL } ) );
}

void append_stmt( void *p, char *s ){
  tree *t = p;
  tree y = tpop( t );
  tree x = tpop( t );
  last_child( x )->next = y;
  tpush( t, x );
}

parser build_parser( void *r ){
    parser Integer = some( char_class( "0123456789" ) );
    parser String = some( char_class( "abcdefghijklmnopqrstuvwxyz" ) );
    parser Id = String;
    parser Expression = empty();
    parser Paren_Expression = sequencen(3, (parser[]){ term('('), Expression, term(')') });
    parser Term = alternaten(3, (parser[]){
          action( Id,              make_id, &r ),
          action( Integer,         make_int, &r ),
                  Paren_Expression
        });
    parser Sum = sequence( Term,
                          many( action( sequence( alternate( term('+'), term('-') ), Term ), make_op, &r ) ) );
    parser Test = sequence( Sum, maybe( action( sequence( term('<'), Sum ), make_op, &r ) ) );
    *Expression = *alternate( Test, sequence( Id, action( sequence( term('='), Expression ), make_op, &r ) ) );
    parser Statement = empty();
    *Statement = *alternaten(3, (parser[]){
          sequencen(4, (parser[]){
            term('{'), maybe( Statement ), many( action( Statement, append_stmt, &r ) ), term('}') } ),
          action( sequence( Expression, term(';') ), make_expr_stmt, &r ),
          action( term(';'), make_empty_stmt, &r )
        });
    parser Program = sequence( Statement, many( action( Statement, append_stmt, &r ) ) );
    return  Program;
}

tree parse_program(char *s){
  static parser p = NULL;
  static tree r = NULL;
  if(  !p  ) p = build_parser( &r );
  return  r = NULL, parse(p, s), r;
}

[toc] | [next] | [standalone]

#141146

On 2/16/2019 4:23 PM, luser droog wrote:
> Going further with the parser combinator code, I took the example
> EBNF grammar for TinyC from
> 
>    https://tomassetti.me/ebnf/
> 
> and using a large "swath" of the grammar I'm trying to construct
> an Abstract Syntax Tree with my parsers.
> 
<snip>

That is not an AST, that looks more like a Concrete Syntax Tree.

An AST would reflect the structural and functional elements of the tree, 
but would not retain the tokens which go into creating them (nor 
necessarily strictly follow the structure of the source program).


But, yeah, there are several conventional ways to construct an AST:
   tag union (seems to be reasonably popular);
   struct-casting (this is a nasty style IMO);
   cons cells (source-language transformed into a Lisp-like form);
   key/value tagged objects (not sure of a better term).
     I am not currently aware of anyone else using these.


Tag union and struct casting appear to be the most popular strategies in 
the compilers I have looked at.

I have used cons cells (and XML DOM) in the past, but currently lean 
against these (both have some notable drawbacks).

My current general preference here is key/value objects.


== Tag Union ==

So, assume:
   enum ast_nodetag_e {
     AST_NT_NONE,	//special/invalid node
     AST_NT_REF,		//variable reference / identifier
     AST_NT_INT,		//integer literal
     AST_NT_STRING,	//string literal
     AST_NT_BINARY,	//binary expression
     AST_NT_UNARY,	//unary expression
     AST_NT_CAST,	//type-case
     AST_NT_IF,		//if statement or ternary operator
     AST_NT_CALL,	//function call
     //...
   };

A tag-union style nodetype:
   typedef struct ast_node_s ast_node;
   struct ast_node_s {
     ast_node *next;	//next node in linked-list tree
     short itag;		//node type tag
     short sfn;		//source filename index
     int sln;		//source line number
     union {
       struct {
         char *name;
       }nt_ref;
       struct {
         uint64_t val;
         uint8_t sfx;
       }nt_int;
       ...
       struct {
         uint8_t op;
         ast_node *nlhs;
         ast_node *nrhs;
       }nt_binary;
       ...
       struct {
         ast_node *ncond;
         ast_node *nthen;
         ast_node *nelse;
       }nt_if;
       ...
     }u;
   };

An advantage of this is that it can be expressed fairly 
straightforwardly in C, and is reasonably efficient to access. Memory 
cost is intermediate (the nodes have the cost of the worst-case node type).


One big drawback is that printing/parsing these types of nodes will 
typically take nearly as much code as the parser itself. Another 
drawback is that they tend to end up with enough "secondary costs" to 
eat what advantages they might otherwise have compared with a key/value 
approach in this use-case.


== Struct Casting ==

Basically similar to the tag union case, except one has a whole lot of 
structs with the first few members in common, and casts between them.

This approach can reduce the memory cost somewhat (if nodes are 
allocated via a pool allocator), but is a bit ugly IMO.

An intermediate is using a node-specific-pointer and (possibly) an 
inline fixed-payload area for smaller nodes, combined with struct-casting.

Ex:
   struct ast_node_s {
     ast_node *next;	//next node in linked-list tree
     short itag;		//node type tag
     short sfn;		//source filename index
     int sln;		//source line number
     void *data;		//node-specific pointer
     char fixdata[32];	//for node-types that fit (*)
   };

*: The size of the fixed-data area would be large enough that the vast 
majority of nodes fit, but generally less than the worst-case. This can 
be used to reduce overall memory cost if compared with tag-union.


Note that typically, ASTs like this will need something like a custom 
pool allocator, as trying to do non-trivial ASTs via normal "malloc()" 
calls will typically eat huge amounts of memory and perform badly IME 
(depending some on C library specifics).


== Cons Cells ==

A cons cell is a fixed-form node typically consisting of a pair of 
dynamically-typed references (traditionally named 'car' and 'cdr').

Here, I will define 'ast_tagref_t' as a special type, large enough to 
represent a pointer, and typically with a lot of bit-twiddly to encode 
other types of value.

   struct ast_cons_s {
     ast_tagref_t car;
     ast_tagref_t cdr;
   };

These cells are organized into linked-lists, usually with the 'car' 
holding a data member, and 'cdr' either pointing to the next node or to 
NULL.

An advantage is that these can represent nearly any tree structure in a 
reasonably generic way, and printing/parsing these trees is reasonably 
straightforward (once the needed support logic is in place).

Traditionally, these are expressed in "S-Expression" syntax, eg:
   (if (cmp :gt x y) x y)

Where each item between the parens is a cons cell.


Drawbacks:
They basically require dragging around a dynamic typesystem to support them;
Kinda awkward to work with from C;
Designs built from cons cells tend to be prone to a certain amount of 
"brittleness";
Overall memory cost tends to be reasonably bad (representing a 
non-trivial AST often takes an much larger number of cons cells vs other 
node types; so the other types of node work out cheaper even though the 
nodes cost more individually).

The brittleness of the tree can be reduced by making things less 
dependent on position "(if :cond c :then x :else y)", but this makes the 
memory overhead a fair bit worse (leading to a pattern of some 
fixed-position members typically followed by flexible optional members).


Actually, naive XML DOM trees are worse memory-wise than cons cells, but 
given how DOM works, this isn't saying much.



== Key/Value Objects ==

Nodes might be structured as:
   typedef struct ast_keynode_s ast_keynode;
   struct ast_keynode_s {
     ast_keynode *next;	//next node in linked-list tree
     uint16_t itag;	//node type tag
     short sfn;		//source filename index
     int sln;		//source line number
     uint8_t nkey;	//number of keys in node
     uint8_t mkey;	//max (allocated) keys, or 0
     uint16_t fixkey[6];	//fixed keys
     uint64_t fixval[6];	//fixed values
   };

In this case, the 'key' holds the "name" of the member, combined with 
some bits encoding what sort of member it is 
(int/float/string/symbol/node/...).

In my compilers, this has generally been a 4.12 split (4 bit key-type, 
12 bits for 'name'). The node tag follows a similar pattern, with the 
high 4 bits for "special" node types.

The 'val' holds the value for a given key, which is coerced to/from the 
appropriate type.

If the node holds fewer than 6 or so keys, they can be directly 
expressed inline, otherwise the node stores them separately (using the 
'fixval' elements as array pointers; or this node becomes the root node 
of a B-Tree).

Note that for a small number of keys, generally linear search works out 
faster, but in cases when the number of keys gets larger, it makes sense 
to keep them sorted and use binary search instead (if overflowing to 
arrays).

It is also possible to overflow the nodes B-Tree style (instead of 
allocating key/value arrays), which works out better from a memory 
management POV (avoids the issues resulting from needing to allocate 
variable-sized memory blocks for arrays), but is a bit more complicated 
to implement (mkey would be replaced with a B-Tree depth; 0=leaf (0..6 
keys); 1=7..36 keys, 2=37..216 keys, ...).

Typically, B-Tree requires a recursive lookup, and inserting a new key 
may result in node splitting. For ASTs, it may also be sane to limit 
depth to 1 (deeper trees are unlikely to occur).


Typically, get/set functions would be used to get/set keys, ex:
   int64_t AST_GetNodeInt(ast_keynode *n, uint16_t key);
   void AST_SetNodeInt(ast_keynode *n, uint16_t key, uint64_t val);
   double AST_GetNodeFloat(ast_keynode *n, uint16_t key);
   void AST_SetNodeFloat(ast_keynode *n, uint16_t key, double val);
   ...

With the key in this case only encoding the 'name' (such as from an 
emum, define, or some other means of mapping a name to a numeric index).

These can also be further wrapped as needed for commonly used node keys:
   ast_keynode *AST_GetNodeBody(ast_keynode *n);
   char *AST_GetNodeRefName(ast_keynode *n);
   ...


This has the advantage of being reasonably memory dense (roughly on-par 
with the tagged union approach).

Like with cons cells, these also allow for a reasonably straightforward 
serialization (such as a JSON-like notation, or can be made to mimic XML 
if needed, *), without the drawback of needing to drag along a dynamic 
type-system to do so.

*: { tag: #foo, cond: X, ... } => <foo ...> <cond>X</cond> ... </foo>
   This isn't too far off from how my BGBCC compiler currently works.


The costs of extra code needed to get/set fields is saved by less code 
in other areas, and the added performance cost of getting/setting fields 
is not generally significant IME (most of the time is generally spent in 
other areas).


Note though, that it is generally a pretty good idea to use some form of 
small integer keys, as trying to use strings as keys (and strcmp) will 
result in a fair bit of memory-waste and performance cost.


For related reasons, for symbols which exist in the source program, it 
also makes sense to intern them into a big string table (so that direct 
pointer or offset comparisons may be used instead of "strcmp()" calls).

Typically for source-program symbols, note that number of unique symbol 
names in a non-trivial program may easily exceed the range of a 16-bit 
value (so, AST node keys would not be used for symbols which exist in 
the source program, only for those needed to express an AST and similar).

So, for example, for looking up global symbols, it may make sense to 
both intern the symbol name, and also use chain-hashing or similar for 
performing lookups.


Others may disagree on some of this...

...

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

#141154

On Tuesday, February 19, 2019 at 3:14:30 PM UTC-6, BGB wrote:
> On 2/16/2019 4:23 PM, luser droog wrote:
> > Going further with the parser combinator code, I took the example
> > EBNF grammar for TinyC from
> > 
> >    https://tomassetti.me/ebnf/
> > 
> > and using a large "swath" of the grammar I'm trying to construct
> > an Abstract Syntax Tree with my parsers.
> > 
> <snip>
> 
> That is not an AST, that looks more like a Concrete Syntax Tree.
> 
> An AST would reflect the structural and functional elements of the tree, 
> but would not retain the tokens which go into creating them (nor 
> necessarily strictly follow the structure of the source program).
> 
> 
> But, yeah, there are several conventional ways to construct an AST:
>    tag union (seems to be reasonably popular);
>    struct-casting (this is a nasty style IMO);
>    cons cells (source-language transformed into a Lisp-like form);
>    key/value tagged objects (not sure of a better term).
>      I am not currently aware of anyone else using these.
> 
> 
> Tag union and struct casting appear to be the most popular strategies in 
> the compilers I have looked at.
> 
> I have used cons cells (and XML DOM) in the past, but currently lean 
> against these (both have some notable drawbacks).
> 
> My current general preference here is key/value objects.
> 

Very interesting breakdown. Thanks for this. I suppose you're right
that my tree is not very abstract. I think that's okay for my 
immediate purposes. I plan to make a formatting tool before making
a compiler. And for a formatting tool, what I need is a tree that
faithfully represents the text that was typed while also having 
all the needed structural information to make formatting decisions.

I'm currently working on where to add "whitespace eaters" into my
grammar and how to attach that whitespace to the token so it can
be considered during tree traversal. 

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

#141155

On Tue, 19 Feb 2019 19:51:49 -0800 (PST), luser droog wrote:
>Very interesting breakdown. Thanks for this. I suppose you're right
>that my tree is not very abstract. I think that's okay for my 
>immediate purposes. I plan to make a formatting tool before making
>a compiler. And for a formatting tool, what I need is a tree that
>faithfully represents the text that was typed while also having 
>all the needed structural information to make formatting decisions.
>
>I'm currently working on where to add "whitespace eaters" into my
>grammar 

>and how to attach that whitespace to the token so it can
>be considered during tree traversal. 

one program language without white spaces has readability == 0

the true because program now are more readable it is not because they
invent loop instructions (for break ecc) and structural instructions
but main, because **indentation** and visual rememeber of loop
and using indentation and spaces for show rendundance in the code...

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

#141156

Rosario19 <Ros@invalid.invalid> writes:

> On Tue, 19 Feb 2019 19:51:49 -0800 (PST), luser droog wrote:
>>Very interesting breakdown. Thanks for this. I suppose you're right
>>that my tree is not very abstract. I think that's okay for my 
>>immediate purposes. I plan to make a formatting tool before making
>>a compiler. And for a formatting tool, what I need is a tree that
>>faithfully represents the text that was typed while also having 
>>all the needed structural information to make formatting decisions.
>>
>>I'm currently working on where to add "whitespace eaters" into my
>>grammar 
>
>>and how to attach that whitespace to the token so it can
>>be considered during tree traversal. 
>
> one program language without white spaces has readability == 0

Not really. If you can still use tab for indents, you're ok.

int main(){
   int a=42;
   int b=33;
   if((a<b)||(33==b)){
      printf("less\n");}
   else{
      printf("more\n");}
   return(0);}
   
> the true because program now are more readable it is not because they
> invent loop instructions (for break ecc) and structural instructions
> but main, because **indentation** and visual rememeber of loop
> and using indentation and spaces for show rendundance in the code...

Don't use spaces other than where required to separate tokens, and for
indentation (spaces pay more than tabs).  But don't use them in
expression: they're misleading!

    a = b+c * d; // spaces fail all the time.

Instead, use parentheses:

    a=(b+(c*d));
    
-- 
__Pascal J. Bourguignon__
http://www.informatimago.com

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

#141730

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:

> Rosario19 <Ros@invalid.invalid> writes:
>
>> [..concerning whitespace in program source..]
>>
>> one program language without white spaces has readability == 0
>
> Not really.  If you can still use tab for indents, you're ok.
>
> int main(){
>    int a=42;
>    int b=33;
>    if((a<b)||(33==b)){
>       printf("less\n");}
>    else{
>       printf("more\n");}
>    return(0);}
>
>> the true because program now are more readable it is not because
>> they invent loop instructions (for break ecc) and structural
>> instructions but main, because **indentation** and visual
>> rememeber of loop and using indentation and spaces for show
>> rendundance in the code...
>
> Don't use spaces other than where required to separate tokens, and
> for indentation (spaces pay more than tabs).  But don't use them
> in expression:  they're misleading!
>
>     a = b+c * d; // spaces fail all the time.
>
> Instead, use parentheses:
>
>     a=(b+(c*d));

This advice has it exactly backwards.  For visual separation,
spaces are better than parentheses because they are a better
match to human perceptual hardware.  For semantic grouping,
variable spacing is better than parentheses, both because it is
more readily perceived, and because it offers a redundancy that
can be used as a check on what the author intended.  The
"misleadingness" in the example (and other similar examples) can
be programmatically detected, and provides a tipoff that there is
something wrong - either a misunderstanding on the part of the
author, or a mistake in the algorithm, or perhaps both.  Using
spacing to (redundantly) show grouping adds useful information.
Taking out all spaces and putting in redundant parentheses takes
away information that is often useful - a losing proposition all
the way around.

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

#141733

On Wednesday, March 6, 2019 at 11:34:10 AM UTC-5, Tim Rentsch wrote:
> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
> > Don't use spaces other than where required to separate tokens, and
> > for indentation (spaces pay more than tabs).  But don't use them
> > in expression:  they're misleading!
> >
> >     a = b+c * d; // spaces fail all the time.
> >
> > Instead, use parentheses:
> >
> >     a=(b+(c*d));
> 
> This advice has it exactly backwards.  For visual separation,
> spaces are better than parentheses because they are a better
> match to human perceptual hardware.

I disagree categorically.   I use parenthesis for separation
on a large number of things, including:

    ((x) ? a : b)

The parenthesis visually break things out, and unquestionably
categorize the orders of operation.

I advise using parenthesis and not spaces.

-- 
Rick C. Hodgin

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

#141746

On Wednesday, March 6, 2019 at 9:02:23 AM UTC-8, Rick C. Hodgin wrote:
> On Wednesday, March 6, 2019 at 11:34:10 AM UTC-5, Tim Rentsch wrote:
> > "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
> > > Don't use spaces other than where required to separate tokens, and
> > > for indentation (spaces pay more than tabs).  But don't use them
> > > in expression:  they're misleading!
> > >
> > >     a = b+c * d; // spaces fail all the time.
> > >
> > > Instead, use parentheses:
> > >
> > >     a=(b+(c*d));
> > 
> > This advice has it exactly backwards.  For visual separation,
> > spaces are better than parentheses because they are a better
> > match to human perceptual hardware.
> 
> I disagree categorically.   I use parenthesis for separation
> on a large number of things, including:
> 
>     ((x) ? a : b)
> 
> The parenthesis visually break things out, and unquestionably
> categorize the orders of operation.
> 
> I advise using parenthesis and not spaces.
> 

Well going a bit off topic, in the pathological case, spaces might actually *break* the hard drive when the code gets stored to the drive.

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

#141756

On 07/03/2019 06:02, Rick C. Hodgin wrote:
> On Wednesday, March 6, 2019 at 11:34:10 AM UTC-5, Tim Rentsch wrote:
>> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>>> Don't use spaces other than where required to separate tokens, and
>>> for indentation (spaces pay more than tabs).  But don't use them
>>> in expression:  they're misleading!
>>>
>>>      a = b+c * d; // spaces fail all the time.
>>>
>>> Instead, use parentheses:
>>>
>>>      a=(b+(c*d));
>>
>> This advice has it exactly backwards.  For visual separation,
>> spaces are better than parentheses because they are a better
>> match to human perceptual hardware.
> 
> I disagree categorically.   I use parenthesis for separation
> on a large number of things, including:
> 
>      ((x) ? a : b)
> 
> The parenthesis visually break things out, and unquestionably
> categorize the orders of operation.
> 
> I advise using parenthesis and not spaces.

Unit tests trump both :)

-- 
Ian.

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

#141757

On Wednesday, March 6, 2019 at 8:11:22 PM UTC-5, Ian Collins wrote:
> On 07/03/2019 06:02, Rick C. Hodgin wrote:
> > I disagree categorically.   I use parenthesis for separation
> > on a large number of things, including:
> > 
> >      ((x) ? a : b)
> > 
> > The parenthesis visually break things out, and unquestionably
> > categorize the orders of operation.
> > 
> > I advise using parenthesis and not spaces.
> 
> Unit tests trump both :)

What are you selling, Ian?  Do you want us to buy some of your
Unit Test Sauce? :-)

-- 
Rick C. Hodgin

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

#141758

On 07/03/2019 14:48, Rick C. Hodgin wrote:
> On Wednesday, March 6, 2019 at 8:11:22 PM UTC-5, Ian Collins wrote:
>> On 07/03/2019 06:02, Rick C. Hodgin wrote:
>>> I disagree categorically.   I use parenthesis for separation
>>> on a large number of things, including:
>>>
>>>       ((x) ? a : b)
>>>
>>> The parenthesis visually break things out, and unquestionably
>>> categorize the orders of operation.
>>>
>>> I advise using parenthesis and not spaces.
>>
>> Unit tests trump both :)
> 
> What are you selling, Ian?  Do you want us to buy some of your
> Unit Test Sauce? :-)

Like so many programmers, I tend to forget all of the C
precedence rules, but failing a test soon reminds me when I get it wrong....

-- 
Ian.

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

#141759

On Wednesday, March 6, 2019 at 8:21:40 PM UTC-6, Ian Collins wrote:
> On 07/03/2019 14:48, Rick C. Hodgin wrote:
> > On Wednesday, March 6, 2019 at 8:11:22 PM UTC-5, Ian Collins wrote:
> >> On 07/03/2019 06:02, Rick C. Hodgin wrote:
> >>> I disagree categorically.   I use parenthesis for separation
> >>> on a large number of things, including:
> >>>
> >>>       ((x) ? a : b)
> >>>
> >>> The parenthesis visually break things out, and unquestionably
> >>> categorize the orders of operation.
> >>>
> >>> I advise using parenthesis and not spaces.
> >>
> >> Unit tests trump both :)
> > 
> > What are you selling, Ian?  Do you want us to buy some of your
> > Unit Test Sauce? :-)
> 
> Like so many programmers, I tend to forget all of the C
> precedence rules, but failing a test soon reminds me when I get it wrong....
> 

I made mnemonic once, but I forgot it. lol

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

#141760

On Wednesday, March 6, 2019 at 8:28:28 PM UTC-6, luser droog wrote:
> On Wednesday, March 6, 2019 at 8:21:40 PM UTC-6, Ian Collins wrote:
> > On 07/03/2019 14:48, Rick C. Hodgin wrote:
> > > On Wednesday, March 6, 2019 at 8:11:22 PM UTC-5, Ian Collins wrote:
> > >> On 07/03/2019 06:02, Rick C. Hodgin wrote:
> > >>> I disagree categorically.   I use parenthesis for separation
> > >>> on a large number of things, including:
> > >>>
> > >>>       ((x) ? a : b)
> > >>>
> > >>> The parenthesis visually break things out, and unquestionably
> > >>> categorize the orders of operation.
> > >>>
> > >>> I advise using parenthesis and not spaces.
> > >>
> > >> Unit tests trump both :)
> > > 
> > > What are you selling, Ian?  Do you want us to buy some of your
> > > Unit Test Sauce? :-)
> > 
> > Like so many programmers, I tend to forget all of the C
> > precedence rules, but failing a test soon reminds me when I get it wrong....
> > 
> 
> I made mnemonic once, but I forgot it. lol

Found it through google groups. I think the 3D effect got broken somehow.

Path: g2news2.google.com!postnews.google.com!l37g2000vba.googlegroups.com!not-for-mail
From: mij...@yahoo.com
Newsgroups: comp.lang.c
Subject: Re: Remebering the order of precedence
Date: Sun, 22 Feb 2009 21:02:53 -0800 (PST)
Organization: http://groups.google.com
Lines: 70
Message-ID: <00248698-9c4b-49a2-a3bc-c31ef388734d@l37g2000vba.googlegroups.com>
References: <db8b2ec1-63ae-4c51-bf1f-ffeac69336a2@o2g2000prl.googlegroups.com>
NNTP-Posting-Host: 75.37.214.99
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1235365373 30575 127.0.0.1 (23 Feb 2009 05:02:53 GMT)
X-Complaints-To: groups...@google.com
NNTP-Posting-Date: Mon, 23 Feb 2009 05:02:53 +0000 (UTC)
Complaints-To: groups...@google.com
Injection-Info: l37g2000vba.googlegroups.com; posting-host=75.37.214.99; 
	posting-account=G1KGwgkAAAAyw4z0LxHH0fja6wAbo7Cz
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux i586; en-US; rv:1.9.0.4) 
	Gecko/2008112309 Iceweasel/3.0.4 (Debian-3.0.4-1),gzip(gfe),gzip(gfe)
Xref: g2news2.google.com comp.lang.c:48975

On Feb 18, 6:47=A0pm, karthikbalaguru <karthikb...@gmail.com>
wrote:
> Hi,
>
> Is there a technique to easily remember the order of precedence
> of all C operators from high to low priority ?
>
> I think this will save time rather than referring to the chart
> for every expression.
> Any ideas ?
>
> Thx in advans,
> Karthik Balaguru

I've been thinking about this since reading your post
and here's my contribution:

I started with the chart itself and added a description
for each line.
1. () [] -> .     explicit access
2. ! ~ ++ -- (type)    unary
   -(unary) *
   & sizeof
3. * / %    mul
4. + -    add
5. << >>   shift
6. < <=3D > >=3D    g|l t|e glute? glitter?
7. =3D=3D !=3D    (n)eq
8. & (bitwise and)    bitand
9. ^    bitxor
10. |    bitor
11. &&   and
12. ||   or
13. ?:   ternary
14. =3D +=3D -=3D etc.   assign
15. ,    comma

and recursively on the binaries:
explicit-access unary
(mul add shift     math
glitter neq     comp
bit(and,xor,or)    bits
and or)  [[binary]]  logic
ternary assign comma.

and finally:
explicit-access unary
binary(math(mul add shift)
 comp(glitter neq)
 bits(and,xor,or)
 logic(and,or))
ternary assign comma.

you can remove the parentheses if you can remember
and before or (xor in the middle)
mul add shift (not too hard)
one applies glitter to a neck, not the other way round.
(the =3D=3D !=3D is a larger branch of the tree than > <
when both occur at the same syntactic level).
math comp bits logic (say it till it rolls off the tongue)

then it's briefly:
explicit-access unary
binary
ternary assign comma


this should help with concision if nothing else.

luXer-ex-troXX

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

#141761

On Wednesday, March 6, 2019 at 9:21:40 PM UTC-5, Ian Collins wrote:
> On 07/03/2019 14:48, Rick C. Hodgin wrote:
> > On Wednesday, March 6, 2019 at 8:11:22 PM UTC-5, Ian Collins wrote:
> >> On 07/03/2019 06:02, Rick C. Hodgin wrote:
> >>> I disagree categorically.   I use parenthesis for separation
> >>> on a large number of things, including:
> >>>
> >>>       ((x) ? a : b)
> >>>
> >>> The parenthesis visually break things out, and unquestionably
> >>> categorize the orders of operation.
> >>>
> >>> I advise using parenthesis and not spaces.
> >>
> >> Unit tests trump both :)
> > 
> > What are you selling, Ian?  Do you want us to buy some of your
> > Unit Test Sauce? :-)
> 
> Like so many programmers, I tend to forget all of the C
> precedence rules, but failing a test soon reminds me when I get it wrong....


I only mention this because I care, Ian:  There are a lot of
decaffeinated brands on the market that are just as tasty as
the real thing.

-- 
Rick C. Hodgin

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

#141763

On Wednesday, March 6, 2019 at 8:47:41 PM UTC-6, Rick C. Hodgin wrote:
> On Wednesday, March 6, 2019 at 9:21:40 PM UTC-5, Ian Collins wrote:
> > On 07/03/2019 14:48, Rick C. Hodgin wrote:
> > > On Wednesday, March 6, 2019 at 8:11:22 PM UTC-5, Ian Collins wrote:
> > >> On 07/03/2019 06:02, Rick C. Hodgin wrote:
> > >>> I disagree categorically.   I use parenthesis for separation
> > >>> on a large number of things, including:
> > >>>
> > >>>       ((x) ? a : b)
> > >>>
> > >>> The parenthesis visually break things out, and unquestionably
> > >>> categorize the orders of operation.
> > >>>
> > >>> I advise using parenthesis and not spaces.
> > >>
> > >> Unit tests trump both :)
> > > 
> > > What are you selling, Ian?  Do you want us to buy some of your
> > > Unit Test Sauce? :-)
> > 
> > Like so many programmers, I tend to forget all of the C
> > precedence rules, but failing a test soon reminds me when I get it wrong....
> 
> 
> I only mention this because I care, Ian:  There are a lot of
> decaffeinated brands on the market that are just as tasty as
> the real thing.
> 

As a Starbucks Coffee Master, I must disagree! Decaffination is an
extra processing step which has a cost. If the decaf is not noticably
more expensive than the regular coffee from the same brand, then it's
cheap beans.

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

#141740

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>
>> Rosario19 <Ros@invalid.invalid> writes:
>>
>>> [..concerning whitespace in program source..]
>>>
>>> one program language without white spaces has readability == 0
>>
>> Not really.  If you can still use tab for indents, you're ok.
>>
>> int main(){
>>    int a=42;
>>    int b=33;
>>    if((a<b)||(33==b)){
>>       printf("less\n");}
>>    else{
>>       printf("more\n");}
>>    return(0);}
>>
>>> the true because program now are more readable it is not because
>>> they invent loop instructions (for break ecc) and structural
>>> instructions but main, because **indentation** and visual
>>> rememeber of loop and using indentation and spaces for show
>>> rendundance in the code...
>>
>> Don't use spaces other than where required to separate tokens, and
>> for indentation (spaces pay more than tabs).  But don't use them
>> in expression:  they're misleading!
>>
>>     a = b+c * d; // spaces fail all the time.
>>
>> Instead, use parentheses:
>>
>>     a=(b+(c*d));
>
> This advice has it exactly backwards.  For visual separation,
> spaces are better than parentheses because they are a better
> match to human perceptual hardware.  For semantic grouping,
> variable spacing is better than parentheses, both because it is
> more readily perceived, and because it offers a redundancy that
> can be used as a check on what the author intended.  The
> "misleadingness" in the example (and other similar examples) can
> be programmatically detected, and provides a tipoff that there is
> something wrong - either a misunderstanding on the part of the
> author, or a mistake in the algorithm, or perhaps both.  Using
> spacing to (redundantly) show grouping adds useful information.
> Taking out all spaces and putting in redundant parentheses takes
> away information that is often useful - a losing proposition all
> the way around.

We are not looking at landscape and scanning for predators here.

We're looking at code that needs to give the human reader a conceptual
structure isomorphe to what the "semantics" implemented by the language
implementation produces.

     a = b+c * d; // spaces fail all the time.

-- 
__Pascal J. Bourguignon__
http://www.informatimago.com

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

#141741

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:
[...]
> We are not looking at landscape and scanning for predators here.
>
> We're looking at code that needs to give the human reader a conceptual
> structure isomorphe to what the "semantics" implemented by the language
> implementation produces.
>
>      a = b+c * d; // spaces fail all the time.

So don't do that.  How often do you actually see code like that?

    a = b + c*d;

It would be nice if compilers warned about misleading spaces in
expressions (perhaps some do).

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

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

#141742

On Wednesday, March 6, 2019 at 12:53:20 PM UTC-5, Keith Thompson wrote:
> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
> [...]
> > We are not looking at landscape and scanning for predators here.
> >
> > We're looking at code that needs to give the human reader a conceptual
> > structure isomorphe to what the "semantics" implemented by the language
> > implementation produces.
> >
> >      a = b+c * d; // spaces fail all the time.
> 
> So don't do that.  How often do you actually see code like that?
> 
>     a = b + c*d;
> 
> It would be nice if compilers warned about misleading spaces in
> expressions (perhaps some do).


It's not the compiler's job to enforce any kind of source code
spacing or code arrangement, but only syntax.

There are surely tools which can provide feedback on where source
code deviates from a coding style, such as not being in ANSI form
or some other well-known standard.

Why pollute a compiler with such arbitrary nonsense?  Was the code
generated by a tool?  Should it have proper spacing?  Those are
not considerations for the compiler.

Only syntax, Keith.  Only syntax.

-- 
Rick C. Hodgin

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

#141744

Keith Thompson <kst-u@mib.org> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
> [...]
>> We are not looking at landscape and scanning for predators here.
>>
>> We're looking at code that needs to give the human reader a conceptual
>> structure isomorphe to what the "semantics" implemented by the language
>> implementation produces.
>>
>>      a = b+c * d; // spaces fail all the time.
>
> So don't do that.  How often do you actually see code like that?
>
>     a = b + c*d;
>
> It would be nice if compilers warned about misleading spaces in
> expressions (perhaps some do).

Often enough.  But the worst part, is that I never encoutered any C
programmer able to recite from memory the list of all C opertors sorted
by their exact priority level.  Therefore not using systematically
parentheses in any C expressions is a sure way to introduce slimy bugs.

(I'm not able to do it for C either, when I programmed in pascal, I
could do it for pascal operators).

-- 
__Pascal J. Bourguignon__
http://www.informatimago.com

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

#141748

On 06/03/2019 18:49, Pascal J. Bourguignon wrote:
> Keith Thompson <kst-u@mib.org> writes:
> 
>> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>> [...]
>>> We are not looking at landscape and scanning for predators here.
>>>
>>> We're looking at code that needs to give the human reader a conceptual
>>> structure isomorphe to what the "semantics" implemented by the language
>>> implementation produces.
>>>
>>>       a = b+c * d; // spaces fail all the time.
>>
>> So don't do that.  How often do you actually see code like that?
>>
>>      a = b + c*d;
>>
>> It would be nice if compilers warned about misleading spaces in
>> expressions (perhaps some do).
> 
> Often enough.  But the worst part, is that I never encoutered any C
> programmer able to recite from memory the list of all C opertors sorted
> by their exact priority level.  Therefore not using systematically
> parentheses in any C expressions is a sure way to introduce slimy bugs.

One or two here claim to know the precedences by heart, notably Tim Rentsch.

It gets dangerous when they expect everyone else to know them, so their 
own code is largely devoid of parentheses.

> (I'm not able to do it for C either, when I programmed in pascal, I
> could do it for pascal operators).


C is a basket-case because there are so many precedences (10 just for 
binary operators, which is a little crazy (have == and <= different, and 
which one is higher and which lower?), and many are unintuitive.

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

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web