[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci & Eng Dept] / [R J Botting] / [Samples] / br.d
[Index] [Contents] [Source Text] [About] [Notation] [Copyright] [Comment/Contact] [Search ]
Fri Sep 19 12:20:35 PDT 2008

Contents


    Analysis and Design of the br Program for UNIX

    WARNING -- old fashioned style, method, and notation

    Introduction

      Name

    1. br

      Author

    2. R J Botting. 1988-1991

      Synopses

    3. br width --- break lines and word wrap input

      Bugs

      This program fails if the expected width of a word wrapped line in characters exceeds the maximum integer stored on the machine.

    . . . . . . . . . ( end of section Introduction) <<Contents | End>>

    Requirements

      Context DFD

                        user
                         |w
                         V
                    in->(br)->out

      The program reads text input and attempts to reformat it so that no line is longer than 'w' characters by breaking lines at the first block of whitespace after the last word that fits on the line. The break is done by removing all the whitespace characters after the last word that fits on the output line and replacing them by CR. Assume that there are no BS chars in the file. If w>250 or <10 then the program should do nothing and report an abnormal termination("error"). Default width is 79. If a single word is too long to fit on a line by itself then it will have to be broken up - Hyphenate words whose length is>w-1.

      Data dictionary

      Input lines (ilines) must be broken up if they are too long. So each iline is split into a group of zero or more shorter output lines followed by part of a line that does not need breaking. The short lines end in the last word that can fit on that line. After the broken lines there is a last part of the iline which is less than 'w' in length, This is ok when each word is smaller than the output line width. Longer words are broken into hyphenated parts.

    1. in::=#iline,
    2. iline::=#( #(word | wsb ) last_word wsb |pt_long_wd ) ok_line,
    3. line::=#(word | wsb ) last_word break |pt_long_wd hyphen eoln,
    4. out::=#( # line ok_line),

    5. ok_line::= #non_eoln eoln,
    6. user::=w.
    7. w::10..250.

      The length of words, wsb and last word in each 'line' add up to less than w and HT (tab) equals HTWIDTH characters in width.

    8. wsb::= #ws,
    9. ws::= HT|SP|non_print,
      Note. Length of HT=HTWIDTH, length of non_print=0.
    10. word::= #non_ws,
    11. last_word::= #last_non_ws,
    12. pt_long_word::= #pt_wd_char. Note. w-1 non_ws chars.
    13. break::= eoln, Alternative: break::=SP eoln, is used by Wordstar to signal a "soft_CR".
    14. break::=eoln HT, would look good. See the brt.c hack.

    15. hyphen::= "-".

    . . . . . . . . . ( end of section Requirements) <<Contents | End>>

    Design

      Note

      In this method the requirements are mapped, definition by definition into a program structure. Each component is named for the data that it consumes (C_) or produces(P_). The operations are extracted from the requirements in a separate process that works backwards from the outputs to the inputs. Then the operations are placed in the structure and an overall design or plan is produced. This is then mapped into the particular language that is needed.

      Correspondences/Program Structure

    1. C_user_C_in_P_out::structure= CU_w; #C_iline,
    2. C_iline::structure= #P_line; CP_ok_line,
    3. P_line::structure= #( CP_word | CP_wsb ); CP_last_word; C_wsb_P_break | CP_pt_long_wd;P_hyphen;P_eoln,
    4. CP_ok_line::structure= #CP_non_eoln; CP_eoln,
    5. CP_wsb::structure= #(CP_HT|CP_non_HT_ws|CP_non_print),
    6. CP_last_word::structure= #CP_last_non_ws,
    7. CP_word::structure= #CP_non_ws,
    8. C_wsb_P_break::structure= #C_ws,
    9. CP_pt_long_word::structure= #CP_pt_wd_char, Note. w-1 non_ws chars.

      Operations List

      The notation is inspired by Tony Hoare's CSP and ":+" operator.
      Table
      SymbolFunctionWhen
      chCharacter
      !chOutput chEach character output
      !eolnOutput end of lineEnd of each output end of line
      ?chInput chEach ch of input
      nNumber of charcters
      n:+1add 1 to nWhen character is output onto line.
      n:+HTWIDTHadd HTWIDTH to neach horizontal tab
      n'=0set n to 0start of a line
      w?:userget width from the userStart of program(or given)
      !"-"Output a hyphenwhen word has to be broken

      (Close Table)

      Program Design

    10. C_user_C_in_P_out::design= w?:user; ?ch; #C_iline,
    11. C_iline::design= #P_line; CP_ok_line,
    12. P_line::design= n'=0; #( CP_word | CP_wsb ); CP_last_word; C_wsb_P_break | CP_pt_long_wd;P_hyphen;P_eoln,

    13. CP_ok_line::design= #CP_non_eoln; CP_eoln,
    14. CP_wsb::design= #(CP_HT|CP_non_HT_ws|CP_non_print),
    15. CP_last_word::design= #CP_last_non_ws,
    16. CP_word::design= #CP_non_ws,
    17. C_wsb_P_break::design= #C_ws; !eoln,
    18. CP_non_eoln::design= !ch; ?ch,
    19. CP_eoln::design= !eoln; ?ch,
    20. CP_HT::design= n:+HTWIDTH; !ch;?ch,
    21. CP_non_HT_ws::design= n:+1; !ch; ?ch,
    22. CP_non_print::design= !ch; ?ch,
    23. CP_non_ws::design= n:+1; !ch; ?ch,
    24. CP_last_non_ws::design= !ch; ?ch,
    25. C_ws::design= ?ch,
    26. CP_pt_long_wd::design= #CP_pt_wd_char,
    27. P_hyphen::design= !"-",
    28. P_eoln::design= !eoln,
    29. CP_pt_wd_char::design= !ch; ?ch,

      Temporal map of Program

           C_user_C_in_P_out
           ________________________________________________________________________
          |    w?:user; ?ch                                                        |
          |________________________________________________________________________|
         /|    C_iline                                                             |\
        | |    ________________________________________________________________    | |
        | |  /| P_line                                                         |\  | |
        | | | |   ___________________________________________________________  | | | |
        | | | |  | n'=0                                     |  CP_pt_long_wd | | | | |
        | | | |  |------------------------------------------|    ----------  | | | | |
        | | | |  |    ______________________    |           |  /| CP_pt_wd|\ | | | | |
        | | | |  |  /|CP_word               |\  |  CP_wsb   | | |  -------| || | | | |
        | | | |  | | |   ________________   | | |           | | | |!ch;?ch| || | | | |
        | | | |  | | | /| CP_non_ws      |\ | | |           | | |  -------| || | | | |
        | | | |  | | || | -------------- | || | |           |  \|_________|/ | | | | |
        | | | |  | | || ||n:+1;!ch; ?ch || || | |           |   | !"-"    |  | | | | |
        | | | |  | | | \| -------------- |/ | | |           |   |---------|  | | | | |
        | | | |  | | |   ----------------   | | |           |   | !eoln   |  | | | | |
        | | | |  |  \|______________________|/  |           |   |_________|  | | | | |
        | | | |  |-----------------------------------------------------------| | | | |
        | | | |  |     CP_last_word                                          | | | | |
        | | | |  |    -----------------                                      | | | | |
        | | | |  |  /|  CP_last_non_ws |\                                    | | | | |
        | | | |  | | |    ---------    | |                                   | | | | |
        | | | |  | | |   |!ch; ?ch |   | |                                   | | | | |
        | | | |  |  \|    ---------    |/                                    | | | | |
        | | | |  |    -----------------                                      | | | | |
        | | | |  |-----------------------------------------------------------| | | | |
        | | | |  |   C_wsb_P_break                                           | | | | |
        | | | |  |    -----------                                            | | | | |
        | | | |  |  /|    C_ws   |\                                          | | | | |
        | | | |  | | |   ------  | |                                         | | | | |
        | | | |  | | |  | ?ch  | | |                                         | | | | |
        | | | |  | | |   ------  | |                                         | | | | |
        | | | |  |  \|-----------|/                                          | | | | |
        | | | |  |   |  !eoln    |                                           | | | | |
        | | | |  |    -----------                                            | | | | |
        | | | |  |___________________________________________________________| | | | |
        | |  \|________________________________________________________________|/  | |
        | |   |      CP_ok_line                                                |   | |
        | |   |   ----------------                                             |   | |
        | |   | /| CP_non_eoln    |\                                           |   | |
        | |   || |    _________   | |                                          |   | |
        | |   || |   |!ch; ?ch |  | |                                          |   | |
        | |   | \|   |_________|  |/                                           |   | |
        | |   |  |----------------|                                            |   | |
        | |   |  | CP_eoln        |                                            |   | |
        | |   |  |    ----------  |                                            |   | |
        | |   |  |   |!eoln; ?ch| |                                            |   | |
        | |   |  |    ----------  |                                            |   | |
        | |   |  |________________|                                            |   | |
        | |   |________________________________________________________________|   | |
         \|________________________________________________________________________|/
      
      
                CP_wsb
          -------------------------------
       (|CP_HT|CP_non_HT_ws|CP_non_print |)
          -------------------------------
      
      
    30. CP_HT::design= n:+HTWIDTH; !ch;?ch
    31. CP_non_HT_ws::design= n:+1; !ch; ?ch
    32. CP_non_print::design= !ch; ?ch

    . . . . . . . . . ( end of section Design) <<Contents | End>>

    Implementation

      DChart Schematic Logic

      wd and ws are buffers
       C_user_C_in_P_out
         \
          | w?:user; ?ch
          | #C_iline
          |  \
          |   | not end(in)
          |   | #P_line(posit iline will be broken after word)
          |   | \2_______________________________________1
          |   |  |admit word not hyphenated              |posit word hyphenated
          |   |  | push ch & wd back out; n'=0           |CP_pt_long_wd
          |   |  | #                                     |  \
          |   |  | \                                     |   |wd!new; n'=0
          |   |  |  |                                    |   |#CP_pt_wd
          |   |  |  |posit room for next word or wsb     |   | \
          |   |  |  |                                    |   |  |n<w;Quit if ch in ws
          |   |  |  |                                    |   | \|wd!ch;n:+1;?ch
          |   |  |  |                                    |   |wd!end;!wd
          |   |  |  |\ _____________________             |   | !'_';!eoln
          |   |  |  | |ch in wdchs          | else       |
          |   |  |  | |CP_word              | CP_wsb    (3)
          |   |  |  | | \                   |  \
          |   |  |  | |  | wd!new           |   |ws!new
          |   |  |  | |  |                  |   |#
          |   |  |  | |  | #CP_non_ws       |   | \
          |   |  |  | |  |  \               |   |  |Quit will be broken if ch=eoln
          |   |  |  | |  |   |              |   |  |
          |   |  |  | |  |   |              |   |  |\ _________________
          |   |  |  | |  |   |ch not ws     |   |  | |      |          |
          |   |  |  | |  |   |Quit if       |   |  | |ch=HT |ch=SP     |ch not SP
          |   |  |  | |  |   |    n=w       |   |  | |      |          |ch not HT
          |   |  |  | |  |   |n:+1;wd!ch    |   | \| |CP_HT |CP_non_HT |CP_non_print
          |   |  |  | |  |  \|?ch           |   |Quit next fits if n>w-1
          |   |  |  | |  |                  |   |ws!end; !ws
          |   |  |  | |wd!end; !wd          |
          |   |  | \|
          |   |  |
          |   |  |admit next did not fit               (3)
          |   |  | CP_last_word                         |
          |   |  |  \                                   |
          |   |  |   side-effects                       |
          |   |  |                                      |
          |   |  |push ch & wd back out (in!b)          |
          |   |  |                                      |
          |   |  | C_wsb_P_break                        |
          |   |  |  \                                   |
          |   |  |   | #C_ws                            |
          |   |  |   |  \                               |
          |   |  |   |   beneficent side-effects        |
          |   |  |   |                                  |
          |   |  |   |!eoln                             |
          |   |  |  \|                                  |
          |   | \|______________________________________|
          |   |
          |   |admit no more breaks needed
          |   |CP_ok_line
          |   | \
          |   |  | #CP_non_eoln
          |   |  |  \
          |   |  |   Beneficient side-effects
          |   |  |
          |   |  |
          |   |  | CP_eoln
          |   |  |  \
          |   |  |   |!eoln; ?ch
      
      
    1. CP_HT::schematic= n:+HTWIDTH; ws!ch;?ch
    2. CP_non_HT_ws::schematic= n:+1; ws!ch; ?ch
    3. CP_non_print::schematic= ws!ch; ?ch

    . . . . . . . . . ( end of section Implementation) <<Contents | End>>

    Source Code

    [ br.c ] [ br.ANSI.c ]

    UNIX Manual

    [ br.l ]

End