edu(b)log

Review for Final Exam

In determining the "goodness" of a programming language, you must find a good balance of what you're looking for — things like readability, writability, reliability, etc.

Syntax issues arise, such as, "How am I going to represent a collection or list — commas, spaces, square brackets, curly braces?"

A lot of things will affect the cost of a language. If you know some Java, it's probably going to be easier to learn C than if you had come from Fortran (you're familiar with int, float, curly braces, etc). You spend less time becoming productive and more time being productive. Because many of our current languages are modeled after existing languages, so the history of programming languages is important.

The movement from machine language to any kind of symbolic (e.g. assembly) language was a big step forward. That jump added readability and writability because it was hard to read and write machine language. The assembly languages did not, however, move toward thinking link a human. You had to think like the architecture (Von Neumann).

Fortran proved that a high level language could be devised that could adjust to the programmer and be useful. There were a lot of constraints on the languages, and their developers didn't make the best choices with array dimensions, statements to include in the langauge, words to represent things, symbols that could be used in more than one way, etc.

One way to improve a language is to find out what the language does to allow programmers to make common errors. New languages can make errors easy to catch and correct or just disallow the error altogether.

Pointers were seen as a step backwards, but they had the ability to deal with dynamic data structures. Pointers made things less readable and more writable. We understand that pointers are error-prone, so languages like Java create dynamic data structures and have all the error-prone pointer functions running in the background.

Support was added to Turbo Pascal that enabled us to deal with objects and instances of objects. We had a sorted dynamic list notion; initial lists were declared to have an initial size and a grow factor. It grows and cleans up after itself and returns to the function when the list needs to grow. Some of the burdens on C programmers have been lifted in languages like Java and Turbo Pascal.

Final Exam Review

The exam will be on WebCT. It must be completed by next Wednesday and once you start it you must finish within three hours.

FAT File System

FAT 12 used 3 nibble numbers which were hard to deal with. You move away from that with FAT 16, although the basics of FAT 12 and 16 are the same. With 12 and 16, you have a fixed size root directory.

With FAT 32, the root directory is out in the data area and may grow as it needs to (so it may be fragmented, etc. though it'll start in cluster 2).

Directories

What does a directory look like? It's a bunch of 32-byte records, and each record represents either what we'd consider to be a DOS directory entry (file or directory) or a long file name. It contains all of the information you need about the file except for the long file name. The LFN is an add-on/hack that Microsoft came up with. LFNs came along in FAT 16 and backtracked into FAT 12 with what we call the vFAT. Entries in vFAT are identified with an invalid flag byte.

A normal directory entry contains the short name, file size, starting cluster, and temporal information (time/date stamps). When we're looking at that information it will be all collected together in the 32 byte directory. The only missing element is the long file name.

Each directory entry points to a starting cluster and to a place in the FAT where the cluster chain for the rest of the file is located.

What kind of non-numerical numbers do you find in the FAT? End-of-file (EOF) and bad block markers are common.

What marks the cluster as being available? A zero (0) in the cluster chain shows that the cluster is available for the OS to choose to save a new file.

File Deletion

When you delete a file, the short file name entry is marked with a 0xE5, and the cluster chain is zeroed out. The clusters themselves are not wiped on normal file deletion. That gives us a good chance to recover the files. All of the information needed to locate the file is still in the directory, but it is hidden to the user.

The only time you normally have problems is when a deleted file is fragmented.

The Boot Sector

The information about the file system, including cluster size, sector size, etc. is located in the boot sector.

Some Issues

File Slack: For a four-cluster sector and a very, very small file, it could have file slack in the following form:

Also, when you start to get up to 32k clusters, small files start to take up 32k when they only need a few hundred bytes. Over a whole disk you can have a lot of waste and inefficiency because of this.

NTFS

In NTFS, you'll still have a boot sector with cluster sizes and other fundamental information about the file system. Some of the stuff in the FAT model that's "fudged" gets pulled apart.

Windows 2000 put the Master File Table at the front of the drive, with a mirror file in the middle of the drive with only the first directory containing critical information.

The Bitmap is used to determine allocation/unallocation of clusters.

Deleting Files on NTFS

You go into the Master File Table, find the cluster markings, and unallocate them. The operating system maintains a pointer to the first available slot. The second that you decide to create a new directory or new file, that's the slot that will be assigned. Stuff that has entries high up in the table, that record will be written over very quickly.

The Master File Table

The idea behind the Master File Table (it started out as 32 entries and then jumped to 64 and on up as long as it's full and needs more space) is that the system reserves a chunk of space in which the master file table lives and it won't likely outgrow the reserved space. All directories are non-resident and may be fragmented.

NTFS uses a first-available allocation strategy, and deletions before where the first-available pointer is will change the first-available pointer to point to the deleted file's space on the drive.

Linux, Unix File Systems

Linux defaults to EXT3, but it also uses EXT2 and RIZR? Linux will mount NTFS volumes read-only. The kernels are not yet stable in terms of writing to NTFS (there are some beta programs out there that do it but they can hose the system if they screw up).

EXT3 is a journaling file system, where EXT2 does not do journaling. Journaling keeps track of the major steps taken during the last sessions with a file. That way if the system crashes, you can boot back up to the last known good configuration and recover to the point of the crash. The EXT2 and 3 file systems are based on UFS (Unix File System). UFS is much more complicated than EXT2 and 3. UFS gets to be archaic because it was designed for smaller systems.

UFS is designed to be both fast and reliable, and to be very efficient with small files. Home systems tend to have a lot of small files (~10-12 clusters).

Important Data Structures

Copies of them are stored throughout the system. Just like the MFT is mirrored in the middle of the drive on NTFS, important data structures are copied and scattered throughout the system. The whole files are mirrored, too — not just the first little part of them.

The boot record in Linux is called a Superblock. Linux divides the drive up into block groups and you'll frequently find a copy of the Superblock at the beginning of these block groups. Linux installations use sparse by default, which only puts the copies at the beginning of selected block groups.

On EXT3 drives, changes made to Superblocks are recorded in the journal (so you may find 150 Superblocks in the journal!).

The idea that we're trying to move away from is the amount of drive head movement there is. That's because the information associated with a file isn't stored near the file. You have to go through the global data structure (in NTFS, it's the MFT). In Linux, there is a chunk of information for each block group. It keeps the information in the files local so that head movement is minimized.

Linux also distributes information fairly evenly across the drive (it doesn't use a first-come-first-serve file allocation method).

Partitions still exist in Linux, but now when we have a partition we may lay a file system down on it. That file system will likely be EXT2 or EXT3.

Files may be actual files or hard links, and it's impossible to tell which is which (i.e. two files may point to the same data). There is a counter that keeps track of the number of files that point to a certain piece of data. You will only know whether more than one file points to data by looking into the Inode information.

There are three categories of optional features these file systems may have:

• Compatible Features — existence of a journal. You can mount an EXT3 as an EXT2 (just ignore the journal). A compatible feature will say "this is a feature I can ignore if I have to, but I can still mount and access the files on this system."
• Incompatible Features — e.g. Compression. You might not be able to mount it if you do not understand the compression. These features will disallow the File System from being moutned.
• Read-Only compatible — Under these circumstances you can mount a system read-only but you can't write to it. The type of thing you would find here is large file support. Certain kinds of large file support is read-only compatible (read and understand but not write). Directory structures are not required to be sorted. If you were to mount one that had sorted directories and you tried to write but you didn't know how to use sorted directories, you would mess up some stuff!

Superblocks

The first data structure we should be concered with is the Superblock (analogous to the Boot Record). It is located 1024 bytes from the beginning of the drive. Unlike the boot record, there is no boot code in the Superblock. In the 1024 bytes before the Superblock contains the boot code. Its contents are basic size and configuration information. You'll find copies of it at the beginning of many (if not all) of the block groups.

The Superblock has a signature, which you can search for and find candidate 1024 byte blocks in case the first one got corrupted. Copies of the Superblock arent' all updated at the same time. On top of that, they contain information about which block group they're in so they won't have the same hash value. You must find them by signature and location.

What do we need to know about a block if it's a collection of sectors? How many sectors are in there?? In a 1.44 floppy, there's one sector per cluster and in a 720k floppy there are 2. So it affects your computation there just as it does here. The typical block sizes that you'll find are 1024, 24GB, 4096.

• The total number of blocks in the whole file system…
• the number of blocks per block group…
• the number of reserved blocks preceding the first block group…
• the total number of inodes in the system…
• number of inodes per block group…
• and number of sectors per block are all located in the Superblock.

There is more information in the Superblock, but these are the most important pieces of data for now.

0xEF53 is in bytes 56 and 57. This is on page 405 in the white text book.

The block bitmap manages just the blocks in the Block Group. The Inode Bitmap manages the allocation status of the inodes in the table. The group descriptor contains information describes the group just like the superblock describes the drive (how many free blocks are in the group, how many inodes are free, where the block and inode bitmaps start, etc). If you delete a file in a busy block and it doesn't free up enough information to make the block less than average on the busy scale, that block won't be overwritten for a long time (with some exceptions, of course).

Inodes

The first issue about inodes is one you'd probably expect: they're all the same size. The size is be defined in the superblock. One inode will be allocated to each file and/or directory. Everything has at least one primary inode. Each inode has a number. No two inodes will have the same number as another (they're numbered sequentially down the drive).

In the first group, inodes 1-10 are reserved. The first non-reserved inode will typically point to the superblock. #2 out of the reserved inodes points to the root directory. Inode #1 keeps track of bad blocks. This used to be an interesting place to hide stuff because imaging tools ignored the bad inode group. Bad guys can make inodes in the bad inode block point to good blocks and the tools didn't pick up on this. Now, tools check to see if bad blocks are really bad. If you're on EXT3, inode #8 points to the journal. It's easy to ignore #8 if you want to.

Each inode is the same size and also has the same break-down (fields). It is possible for extended attributes to be set, and if that's the case they'll be stored outside the inode. There will have to be a flag set to show that there are extended attributes. Inside the inode you'll find:

• File size
• Ownership indicator (like GUID number) *Can find the owner in the password file… See Password Data, below.
• Temporal information like MAC (Modify, Access, Change — NOT create!) times and deletion time. *See Time Data below.
• Mode field — typically contains stuff like the file type or link type, if applicable
• Basic permissions — in typical *nix systems, users are members of groups. You can set Read, Write, Execute access for a particular User, Group, and All Users. There are user and group owners, which may have different permissions.
• Link Count — the number of directory entries identifying this inode as the head node for a file. Only hard links affect the link count.

Password Data

The password information is in /etc/passwd. Ownership in an inode doesn't necessarily reflect the fact that the user created the file or even knows it's there because there's a change ownership function you can use to change the ownership of a file.

You may go to the passwd file and there's nothing there. The ID number may not have a user associated with it. Somebody probably went to the web and pulled down a tarball and opened it and the files had ownership associated with them for users on another system.

Time Data

Access (A) time indicates the time the file was last accessed. Last Modify (M) time is the last time the file content was modified. Last Changed (C) time is the last time the metadata was changed. There's also a deletion time.

Notice that there are no file names in the inodes. One of the reasons is that file names may be allowed to be dynamic linked and there's no room in the inodes for dynamic links. You can't go outside the inode like you can with a non-resident entry in an MFT record. You won't see dynamic things in the inode.

Directory entries are located close to their data. Hopefully, if a directory is in a group, the files will be in the group as well.

Inode Types

In addition to the above, "primary" or "direct" Inodes have 12 direct pointers to content blocks. They will have 1 indirect pointer, 1 double indirect pointer, and 1 triple indirect pointer.

Indirect pointers are pointing to 12 other inodes. A double indirect points to an inode that points to 12 other inodes. By the time you get out to the triple (which points to 12 doubles), you have 12⁴ blocks being pointed to.

A fairly simplistic and incomplete version of this:

Files are typically grouped in the same group with a parent directory. This prevents having to move the read head a lot. If it is a new directory, you use that "search for a less used group" function and the file/directory is put there.

With the move command, the data doesn't actually move. The old directory entry is killed and a new one is created.

File Deletion under EXT2/3

When you delete a file, the inode status is set to zero. If a process has a hold of the file, it doesn't unallocate the inode. It breaks the link between the directory entry and the inode. Now you have a file without a parent (an orphan). There's an inode orphan list in the Superblock. When you reboot the computer, the orphans will be unallocated. If you catch it before the reboot, nothing's gone.

There's a difference between EXT2 and EXT3 in terms of unallocating an inode. In EXT3, the file size is set to 0 and the data pointers are wiped. If you recover the inode, you'll have a heck of a time finding the content blocks because the pointers are wiped. EXT2 doesn't wipe the pointers or the file size (similar to FAT).

M, C, and D time are updated to reflect the time of deletion. If the deletion is due to a Move, the A time will be updated as well. If you move a file to another volume, the M time is changed to reflect that.

Directory Entries

Some Stuff for The Final

Flynn's Taxonomy

• SISD → e.g. Von Neumann, Stack Machine
• SIMD → e.g. Array Processors, Parallel Processing
• MISD → e.g. Pipelining Some say that this type of architecture doesn't exist, and others claim that it is pipelining. *See Systolic Arrays, below.
• MIMD → e.g. Multiprocessors (Parallel Processors)

Systolic Arrays can be classified as MISD. Flynn wrote a paper about seven years ago that was a revision of the taxonomy, and he said that MISD are systolic arrays. He considered the array to be a single piece of data floating through multiple instructions. The matrix is considered a data value and you take the matrix and flow it through the array and you do multiple operations on that single data. To do this, you must consider that the value array or matrix is the single data.

In a Data Flow machine, the instructions are executed when all of the data arrives into the instruction. The standard rule is parallelism, so you have a Multiple Instruction Single Data machine.

Why, if you have a CPU and several I/O Devices that are doing work, don't we call it a multiprocessor? The work that's getting done in the I/O devices can't be processed in the I/O device; it has to go back to the CPU for processing.

More on Grammars, etc.

When we type a number like

const x = 6143;
const y = 0xa2b3;

The compiler sees a string of ASCII characters. We are thinking x is storing the number 6143 or hexadecimal a2b3 (decimal 41651). So if we are looking at a hex number…

<hex_num> ::= <hex_digit> | <hex_num> <hex_digit>
<hex_digit> ::= '0'|'1'|'2'|…|'a'|'b'|'c'|'d'|'e'|'f'|'A'|'B'|…|'F'

Now we need an evaluation function (a meaning).

V('0') = 0
V('1') = 1
.
.
V('9') = 9
V('a') = 10
.
.
V('f') = 16
V('A') = 10
.
.
V('F') = 16

We also need "the value of the left-hand side is the value of the right-hand side under those circumstances." Looking at the symantics…

V(<hex_digit_x>) = V('x')

Then we have to deal with the first rule above…

for <hex_num> ::= <hex_digit>
    V(<hex_num>) = V(<hex_digit>)
    value of l.h.s. = val of r.h.s.

<hex_num>[1] ::= <hex_num>[2] <hex_digit>
   V(<hex_num>[1]) = V(<hex_num>[2]) * 16 + V(<hex_digit>)
   value l.h.s. is 16 * val of r.h.s._hex_num + val of hex_digit
   <hex_num> ::= <hex_num> <hex_digit>
             ::= <hex_num> 3
             ::= <hex_num> <hex_digit> 3
             ::= <hex_num> b3
             ::= <hex_num> <hex_digit> b3
             ::= <hex_num> 2b3
             ::= <hex_digit> 2b3
             ::= a2b3

We touched on pre- and post- conditions in class (i.e. a=6 needs a precondition that a is an int and a post-condition that a is equal to 6).

Exceptions are unexpected error conditions (anything unexpected will be an exception that you'll have to deal with). For example, you expect someone to put in a number and they type "twelve" (because they are just not smart). Divide by zero is a type of exception… Range errors (index out of range) lead to buffer overflow, DoS attacks, etc.

C++ was one of the first language to deal with exception handlers. In C++ you throw an exception and in ADA you "raise" an exception. The difference is that C++ didn't use the word "raise" because they had a raise function in another library (they didn't want conflict between the names).

When you start talking about exception handling being built into the language? Are you going to have default exceptions such as divide-by-zero? If you are, you run into a slight problem: you might want to handle them differently in different places. The idea of a zero divide error being an exception, you'd have to say "on zero divide" throw an exception function. You might want to terminate the program gracefully by closing open files and exiting instead of a blue screen of death. In another spot, if you have a count of zero on a list average, you might just want to say "there's no information in the file" and you want to continue processing. You shouldn't have to close the program because you tried to perform a function on a non-existant file.

We also discussed event handlers and where to return to after the handler has done its job. Given that the event could have occurred in a variety of places, how do you call an exception handler?

Read Chapter 14!

Thanks

Thank you Heather C. for your tip! You are officially awesome for giving something back. :o)

Final Exam Study 1

That's right, folks… It's that time again. It seems like these types of questions are going to be on the exam, so familiarize yourself with them and if you see any errors please let me know so that I can fix the site before too many people study incorrect material! This applies to any other page on Edulog… Don't be shy. Thanks!

Question: If we have a two-way set associative cache of size four, using the LRU replacement strategy, how many times would a block be replaced? What are the final blocks in the cache at the end of the program?

Saying that the cache is of size four means that there are four blocks, and it's two-way set associative so there are two blocks per set so there are two sets in all.

***** You need to do (reference mod 2) to get the set and then within the set, LRU is applied. *****

Reference string: 4, 5, 9, 8, 5, 4, 21, 9, 1, 13, 1, 9, 16, 4, 12

Answer:

⇒ 7 replacements, not including the first four inputs into the empty queue… (I guess by assuming that the queue is empty to begin with you don't count the first four inputs as "replacements" although their memory access time will probably be the same).

Question: How many sets are there in a two-way set associative cache with 32kb capacity and 64-byte lines (each block is 64 bytes), and how many bits of the address are used to select a set in this cache?

Answer: There are two lines per set in a two-way set associative cache. If it is at full capacity, we have 512 blocks with two blocks per set, so there are 256 sets. So, we will need eight bits to address a set in the cache.

Write Operation

We have two options here. First, Write Through: The information (values) is written in the cache and in main memory.

The other option is Write Back: The block or line is only written to main memory when it is replaced. All writes are done in cache until replaced.

Misses

• Compulsory Misses: caused by the first reference to a line. The first example we did was compulsory misses.
• Capacity Misses: Occur when the cache can not contain all the blocks needed during execution of a program. Some block has to be replaced.
• Conflict Misses: occur in set associative or direct mapping when references are mapped to the same set.

Question: In a direct-mapped cache with capacity of 16kb and a line length of 32 bytes, how many bits are used to determine the byte (the byte within a word) that a memory operation references in a cache line, and how many bits are used to select the line in the cache?

Answer: 5 and 9, respectively. The toal size of the cache is 16kb where 1kb = 1024 bytes. So, the number of lines in memory is 16 * 1024/32 = 512… log₂ 512 = 9

* You can't apply LRU in direct-mapped.

Grammar Rules with Math

These are the notes exactly from class, but there are lots of [sic] errors in them. Consult the book for this section instead!!

subprog::-<ret_type><name>^[1](<arg_list>) begin <body> end <name>^[2]

<name>^[1].string = <name>^[2].string

S ← nil
S ← <num>,S
<num> ← 0|1|2|3|4|5|6|7|8|9

1. S ← 3,S
2. S ← 4,S
3. S ← 5,S
4. S ← nil

The deviations from average (4) are -1, 0, and +1. To get the deviations, you need to get the average. For the average, you need the total and the count. This grammar can generate a list that is arbitrarily long. To get the sum and the count, you would have to traverse the list. You might traverse the list up to three times, but you should do something like counting and totaling at the same time and pass through the list only once. You can't use the grammar to make that happen.

To keep track of the root, add a rule to your grammar:

Root ← S

The sum is going to come from the values of the children. Nil should get a value of zero and 3, 4, and 5 will have their own respective values. To add, you can start at nil and move up the parse tree. Once the total and count arrive at the root, you can generate the average and send it back down to generate the deviations. To do this we need additional rules. Note that with the following you could generate a divide by zero error.

L.H.S. count = R.H.S. count
L.H.S. sum = R.H.S. sum
(synthesized - get info for parent from child)
L.H.S. average = L.H.S. sum / L.H.S. count
R.H.S. average = L.H.S. average (pass info from parent to child)

S ← nil
L.H.S. count = 0
L.H.S. sum = 0

S ← x,S
L.H.S. count = 1 + R.H.S. count
L.H.S. sum = x + R.H.S. sum
R.H.S. average = L.H.S. average

To avoid the divide by zero error, you could change the rule to

Root ← <num> | <num>,S

…but of course that would add some cases to the rules above.

       R   count = 3, sum = 12, avg = 4 ←
       |
       S   count = 1+2 = 3, sum = 3 + 9 = 12, avg = ? ← 4
      /|\
     3 , S   count = 1+1 = 2, sum = 4+5 = 9, avg = ? ← 4
        /|\
       4 , S   count = 1+0 = 1, sum = 4, avg = ? ← 4
          /|\
         5 , S   count = 0, sum = 0, avg = ? ← 4
             |
            nil

LISP Notes

It's probably a little late for this, but here are some LISP notes sent to me by one of the students in our class. They're much more in depth than what I have on this site and may be helpful for the next LISP assignment and final exam.

Download lispnotes.doc

Project 3

For the final project…

|0> ≡ Vector 0 → |0> = [1]
                        [0]

|1> ≡ Vector 1 → |1> = [0]
                        [1]

Remember that the Identity Matrix looks like the following:

[1 0]
[0 1]

And a nx2 matrix multiplied by the identity will return the nx2 matrix. A "not" matrix looks like the following:

[0 1]
[1 0]

The "not" matrix will make NOT |0> = |1>. In the same way, NOT |1> = |0>. So, NOT acts like an inverter.

|00>
|01>
|10>
|11>

|00> ≡ [1][1] → [1] 0
        [0][0]   [1] 1
                 [0] 2
                 [0] 3

             0
            1 1
             0
             ↓
      [   ][   ][   ] ← 0 0
      [   ][   ][   ]
0 1 → [   ][   ][   ]

      [   ][   ][  0] ← 0
      [   ][   ][   ]
  0 → [1  ][   ][   ]

      [   ][  0][   ]0
      [   ][ 0 ][   ]
     0[   ][1  ][   ]

      [  0][   ][  0]0
      [ 1 ][   ][ 1 ]
     0[0  ][   ][1  ]
     ...

We can represent the output in several ways. For example,

[1  1][1] = [1] = [1] + [0] = |0> + |1>
[1 -1][0]   [1]   [0]   [1]

Note: There are different ways to transform NOT into the Identity matrix. For instance, NOT times NOT equals the Identity matrix.

To implement the systolic array, you need the following set up:

How long does it take to do the computation. Theoretically, it will take 8 + 9 + 8 steps to execute, but depending if you have to implement a comparator it may actually be more. Your design should get the same results as the theoretical design, but if it's slower, you won't lose points.

Grammars to Describe Programming Language Rules

A grammar is a metalanguage that can describe a programming language. From Wikipedia:

Formal grammars fall into two main categories: generative and analytic.

• A generative grammar, the most well-known kind, is a set of rules by which all possible strings in the language to be described can be generated by successively rewriting strings starting from a designated start symbol. A generative grammar in effect formalizes an algorithm that generates strings in the language.
• An analytic grammar, in contrast, is a set of rules that assume an arbitrary string to be given as input, and which successively reduce or analyze that input string yielding a final boolean, "yes/no" result indicating whether or not the input string is a member of the language described by the grammar. An analytic grammar in effect formally describes a parser for a language.

In short, an analytic grammar describes how to read a language, whereas a generative grammar describes how to write it. For example,

S
S::=if <cond> then <stmt>

S is the "start" symbol. The "if" and the "then" are terminal symbols. "Cond" and "stmt" are additional non-terminals (yet to be defined). A rule will be made up of something that looks like a left-hand side, a replacement operator, and a right-hand-side. The right-hand side will be made up of terminals and non-terminals. The above rules describe a context-free grammar.

S
S::=if <bool_exp> then <stmt>
<bool_exp> ::= bool_var and <bool_exp> | 
              bool_var or <bool_exp> |
              bool_var

"And" and "or" usually have special symbols depending on the language it describes, so I've left the words here for this general description.

For the most part, a generational description (like a grammar) is a more effective way of teaching a programmer than, say, learning a language from a compiler. However, a programmer doesn't go back to the grammar to check if something is valid code; they throw it at the compiler and see what it returns.

Subprog ::= <ret_type> <name> ( <arg_list> )
            begin
            <stmt_list>
            end <name>

With non-terminals, you cannot force them to be the same thing in two different places. So, <name> won't necessarily mean the same thing on line 1 as it does on line 4 above.

S → aSa | ab      S → ab
S → aSa → aabb = a2b2
S → aSb → aaSbb → aaabbb = a3b3
               ≡ {anbn | n >= 1 }

There's a small section in Chapter 3 on Attribute Grammars, which allow you to add additional information in. You have a rule for the grammar, and in addition to the rule, you have some attribute functions. So you would have something like

Subprog ::= <ret_type> <name>[1]( <arg_list> )
            begin
            <stmt_list>
            end <name>[1]

And then you would have an attribute rule in addition to the form rule with some additional information like

Rule: <name>[1] = <name>[2]

With this, you can force the <name>s to be the same. So with a C compiler,

x = y + z;

You can check whether y and z may be added together. If y or z are a float and x is an int, the language will know to reject the statement because of a type mismatch.

<assign_stmt> ::= <var> = <exp>
<var> ::= x|y|z
<exp> ::= <var> | <var> | <var>

The tree for this would look something like this (forgive me for not making it pretty for you):

     <assign_stmt>
      /   |    \
   <var>  =  <exp>
     |       / | \
     x   <var> + <var>
            |     |
            y     z

Readability and writability were also important in describing languages. Grammars made it more writable to describe recursion, etc.