Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in
P parabix-devel
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 8
    • Issues 8
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
  • Merge requests 2
    • Merge requests 2
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Operations
    • Operations
    • Incidents
    • Environments
  • Packages & Registries
    • Packages & Registries
    • Container Registry
  • Analytics
    • Analytics
    • CI/CD
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • cameron
  • parabix-devel
  • Wiki
  • Bracket Matching

Bracket Matching · Changes

Page history
Update Bracket Matching authored Feb 09, 2022 by lperesde's avatar lperesde
Hide whitespace changes
Inline Side-by-side
Showing with 38 additions and 4 deletions
+38 -4
  • Bracket-Matching.md Bracket-Matching.md +38 -4
  • No files found.
Bracket-Matching.md
View page @ 8e2c8529
...@@ -39,11 +39,45 @@ object ::= '{' string : [value {',' value}] '}' ...@@ -39,11 +39,45 @@ object ::= '{' string : [value {',' value}] '}'
value ::= object | array | numeral | string | 'true' | 'false' | 'null' value ::= object | array | numeral | string | 'true' | 'false' | 'null'
``` ```
### Validating non-nested JSON
A JSON grammar is given by `JSON ::= value`, meaning that in some instances - `numeral | string | 'true' | 'false' | 'null'` - we do not have nesting. See an example below:
_// string.json_
```
"This is valid JSON"
```
Thus, when we apply NestingDepth kernel to this stream, we get the output:
```
Bracket Stream .....................
Nesting Depth 000000000000000000000
ND BixNum[2] .....................
ND BixNum[1] .....................
ND BixNum[0] .....................
```
Assume that `valueToken` is a bit stream that marks the end position of Assume that `valueToken` is a bit stream that marks the end position of
any legal JSON numeral, string or keyword, while `anyToken` is a bit stream any legal JSON numeral, string or keyword, then the example above would look like:
marking the end position of any legal or illegal token. ```
Assume also that `LBrak`, `RBrak`, and `Comma` are streams marking the valueToken ...................1.
position of JSON `[`, `]`, and `,` tokens respectively. EOFbit ....................1
```
Then we can validate if we have valid non-nesting values by checking:
```
otherND = bnc.UGT(ND, 0)
mix = otherND | valueToken // if only one bit is set, then we don't have other ND
begin = ~Advance(<1>, 1)
firstValue = ScanTo(begin, mix)
nonNestingValue = Advance(firstValue, 1) & EOFbit
err = EOFBit ^ nonNestingValue
```
### Validating arrays
Assume we have two bit streams for tokens: `valueToken` (explained above) and `anyToken`, a bit stream marking the end position of any legal or illegal token. Assume also that `LBrak`, `RBrak`, and `Comma` are streams marking the position of JSON `[`, `]`, and `,` tokens respectively.
Suppose that a BixNum `ND` has been computed as the nesting depth involving Suppose that a BixNum `ND` has been computed as the nesting depth involving
the left and right delimiter sets consisting of square brackets and braces. the left and right delimiter sets consisting of square brackets and braces.
......
Clone repository
  • Bracket Matching
  • CSV Validation
  • CSVediting
  • CSVparsing
  • Character Code Compilers
  • KernelLibrary
  • Pablo
  • ParabixTransform
  • Parallel Deletion
  • Parallel Hashing
  • Performance Testing Script
  • Shuffle Pattern Library
  • StaticCCC
  • String Insertion
  • UCD: Unicode Property Database and Compilers
View All Pages